Merge Range
出处 Insert Interval
给出若干闭合区间,合并所有重叠的部分。
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].
Solution
To check the intersections between interval [a,b] and [c,d], there are four cases (equal not shown in the figures):
a____b
c____d
a____b
c____d
a_______b
c___d
a___b
c_______d
But we can simplify these into 2 cases when check the smaller (smaller start point) interval with the bigger interval.
For the problem, the idea is simple. First sort the vector according to the start value. Second, scan every interval, if it can be merged to the previous one, then merge them, else push it into the result vector.
- compare [1,2] with [4,9], then insert [1,2];
- merge [3,5] with [4,9], get newInterval = [3,9];
- merge [6,7] with [3,9], get newInterval = [3,9];
- merge [8,10] with [3,9], get newInterval = [3,10];
- compare [12,16] with [3,10], insert newInterval [3,10], then all the remaining intervals...
Complexity
时间复杂度 O(n),空间复杂度 O(1)
Code
- Solution 1 : Time O(N).
- Solution 2 : Time O(Log(N)).
public List<Interval> insert_1(List<Interval> intervals, Interval newInterval) {
List<Interval> res = new ArrayList<Interval>();
boolean inserted = false;
for (Interval it : intervals) {
if (inserted || it.end < newInterval.start) {
res.add(it);
} else if (it.start > newInterval.end) {
res.add(newInterval);
res.add(it);
inserted = true;
} else {
newInterval.start = Math.min(newInterval.start, it.start);
newInterval.end = Math.max(newInterval.end, it.end);
}
}
if (inserted == false) res.add(newInterval);
return res;
}
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
List<Interval> res = new ArrayList<Interval>();
int n = intervals.size();
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (intervals.get(mid).start > newInterval.start) right = mid - 1;
else left = mid + 1;
}
int idxStart = right;
left = 0; right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (intervals.get(mid).end < newInterval.end) left = mid + 1;
else right = mid - 1;
}
int idxEnd = left;
if (idxStart >= 0 && newInterval.start <= intervals.get(idxStart).end) {
newInterval.start = intervals.get(idxStart--).start;
}
if (idxEnd < n && newInterval.end >= intervals.get(idxEnd).start) {
newInterval.end = intervals.get(idxEnd++).end;
}
for (int i = 0; i <= idxStart; ++i) {
res.add(intervals.get(i));
}
res.add(newInterval);
for (int i = idxEnd; i < n; ++i) {
res.add(intervals.get(i));
}
return res;
}