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]
. 解题思路: insertion sort 的演变
Java Code:
public Listinsert(List intervals, Interval newInterval) { List res = new ArrayList (intervals); int s = 0; // at index s, the start is correct. we need to merge the end. while(s < intervals.size() && newInterval.start >= intervals.get(s).start){ s++; } if(s > 0 && newInterval.start <= intervals.get(s-1).end){ s--; }else{ res.add(s, newInterval); } res.get(s).end = Math.max(newInterval.end, res.get(s).end); s++; while( s < res.size() && newInterval.end >= res.get(s).start){ newInterval.end = Math.max(newInterval.end, res.get(s).end); res.remove(s); } return res; }
No comments:
Post a Comment