Thought:
Scan the ArrayList-> find the start and end-> deal with the case that newinterval is before the start or after the end-> remove s to e-> insert at s-> get the result
Code:
public class Solution {
public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
int s = -1, e = -1;
for (int i = 0; i < intervals.size(); i++) {
if (s == -1 && intervals.get(i).end >= newInterval.start) {
s = i;
}
if (intervals.get(i).start <= newInterval.end) {
e = i;
}
}
if (s == -1) {
intervals.add(newInterval);
return intervals;
}else if (e == -1) {
intervals.add(0, newInterval);
return intervals;
}
int start = Math.min(intervals.get(s).start, newInterval.start);
int end = Math.max(intervals.get(e).end, newInterval.end);
intervals.subList(s, e+1).clear();
if (s < intervals.size()) {
intervals.add(s, new Interval(start, end));
}else {
intervals.add(new Interval(start, end));
}
return intervals;
}
}
No comments:
Post a Comment