Given a set ofnon-overlappingintervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals[1,3],[6,9], insert and merge[2,5]in as[1,5],[6,9].
Example 2:
Given[1,2],[3,5],[6,7],[8,10],[12,16], insert and merge[4,9]in as[1,2],[3,10],[12,16].
This is because the new interval[4,9]overlaps with[3,5],[6,7],[8,10].
这题也是，先排序，然后通过循环来找新区间插入位置。
public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
ArrayList<Interval> result = new ArrayList<Interval>();
if (intervals == null || newInterval == null) {
return result;
} else if (intervals.size() == 0 && newInterval != null) {
result.add(newInterval);
return result;
}
// don't need to binary search for insert location, do it while adding elem to result
int insertPos = 0;
for (Interval cur : intervals) {
// find intervals that's is outside the new Interval, add them as they are
if (cur.end < newInterval.start) {
result.add(cur);
insertPos++;// keep track of insert postion
} else if (cur.start > newInterval.end) {
result.add(cur);
} else {
// if the current interval intersect with new interval,
// merge them into the new interval
newInterval.start = Math.min(cur.start, newInterval.start);
newInterval.end = Math.max(cur.end, newInterval.end);
}
}
// insert the new interval to correct position then return.
result.add(insertPos, newInterval);
return result;
}