# Merge Range

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.

1. compare [1,2] with [4,9], then insert [1,2];
2. merge [3,5] with [4,9], get newInterval = [3,9];
3. merge [6,7] with [3,9], get newInterval = [3,9];
4. merge [8,10] with [3,9], get newInterval = [3,10];
5. compare [12,16] with [3,10], insert newInterval [3,10], then all the remaining intervals...

## 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) {
} else if (it.start > newInterval.end) {
inserted = true;
} else {
newInterval.start = Math.min(newInterval.start, it.start);
newInterval.end = Math.max(newInterval.end, it.end);
}
}
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) {