Given a list of intervals, merge all the overlapping intervals to produce a list that has only mutually exclusive intervals.
Input: [[1,3], [2,6], [8,10]]
Output: [[1,6], [8,10]Let’s take the example of two intervals such that prev[0] <= cur[0] . Our goal is to merge the intervals whenever they overlap.
The diagram above clearly shows a merging approach.
- 1 Sort the intervals on the start time to ensure
prev[0] <= cur[0] - 2 If prev overlaps cur, we need to merge them into a new interval
csuch that
c[0] = prev[0]
c[1] = Math.max(prev[1], cur[1])- 3 Repeating the above two steps to merge c with the next interval if it overlaps with c
function merge(intervals) {
intervals.sort((a, b) => a[0] - b[0]); let res = [];
let prev = intervals[0]; for (let i = 0; i < intervals.length; i++) {
let cur = interval[i];
if (prev[1] >= cur[0]) {
prev[1] = Math.max(prev[1], cur[1]);
} else {
res.push(prev);
prev = cur; }
}
res.push(prev);
return res;
}
The time complexity of the above algorithm is O(N * logN), where N is the total number of intervals. We are iterating the intervals only once which will take O(N), in the beginning though, since we need to sort the intervals, our algorithm will take O(N * logN).
Given an array of non-overlapping intervals sorted by their start time, insert a given interval at the correct position and merge all necessary intervals to produce an array that has only mutually exclusive intervals.
Our overall algorithm will look like this
- 1 Skip all intervals which end before the start of the new interval. i.e skip all intervals with the following condition
intervals[i].end < newInterval.start- 2 Let’s call the last interval “green” that does not satisfy the above condition. If green overlaps with the new interval “blue” (i.e green.start ≤ blue.end), we will need to merge them into a new interval
blue.start = Math.min(green.start, blue.start)
blue.end = Math.max(green.end, blue.end)We will repeat the above steps to merge the all the green overlapping intervals.
function insert(intervals, newInterval) {
let res = [];
let i = 0;
let length = intervals.length; while (i < length && interval[i][1] < newInterval[0]) {
res.push(intervals[i];
i++;
} while (i < length && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(newInterval[0], interval[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
i++;
}
res.push(newInterval); while (i < length) {
res.push(intervals[i]);
i++;
}
return res;
}
As we are iterating through all the intervals only once, the time complexity of the above algorithm is O(N), where N is the total number of intervals.
Given two lists of intervals, find the intersection of these two lists. Each list consists of disjoint intervals sorted on their start time.
A = [[1,7]], B = [[3,10]]
Output：[[3,7]]The overlapped part will be equal to start = Math.max(A.start, B.start)
end = Math.min(A.end, B.end)
So our algorithm will be to iterate through both array together to see if any two intervals overlap. If two intervals overlap, we will insert overlapped part into a result array and move on to next interval.
function intervalIntersection (A, B) {
let i = 0, j = 0, res = [];
while (i < A.length && j < B.length) {
let start = Math.max(A[i][0], B[j][0]);
let end = Math.min(A[i][1], B[j][1]); if (start <= end) {
res.push([start, end]);
} A[i][1] < B[j][1] ? i++ : j++;
}
return res;
}
As we are iterating through both the lists once, the time complexity of the above algorithm is O(N + M), where N and M are the total number of intervals in the input arrays respectively.
Ignoring the space needed for the result list, the algorithm runs in constant space O(1).
