Linear Algorithm to Merge Intervals

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Merge Intervals Algorithm

We can sort the intervals by the start and then end. Then, going through the intervals, if the next interval is not overlapping the previous merged intervals (we can check this by comparing the start point of the next interval and previous end of the interval).

We can either push the next interval or setting the previous interval ending the maximum or the next interval’s end.

The C++ implementation to merge a list of intervals in linear time complexity is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    vector<vector<int>> mergeIntervals(vector<vector<int>>& intervals) {
        sort(begin(intervals), end(intervals));
        vector<vector<int>> r;
        for (const auto &interval: intervals) {
            if (r.empty() || (r.back()[1] < interval[0])) {
                r.push_back(interval);
            } else {
                r.back()[1] = max(r.back()[1], interval[1]);
            }
        }
        return r;          
    }
};

class Solution {
public:
    vector<vector<int>> mergeIntervals(vector<vector<int>>& intervals) {
        sort(begin(intervals), end(intervals));
        vector<vector<int>> r;
        for (const auto &interval: intervals) {
            if (r.empty() || (r.back()[1] < interval[0])) {
                r.push_back(interval);
            } else {
                r.back()[1] = max(r.back()[1], interval[1]);
            }
        }
        return r;          
    }
};

Python implementation to merge a list of intervals:

1
2
3
4
5
6
7
8
9
10

class Solution:
    def mergeIntervals(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        ans = []
        for a, b in intervals:
            if not ans or ans[-1][1] < a:
                ans.append([a, b])
            else:
                ans[-1][1] = max(ans[-1][1], b)
        return ans

class Solution:
    def mergeIntervals(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        ans = []
        for a, b in intervals:
            if not ans or ans[-1][1] < a:
                ans.append([a, b])
            else:
                ans[-1][1] = max(ans[-1][1], b)
        return ans

See also: Algorithm to Count Intervals Intersecting at Point

Similar algorithm can be used to summarize/merge Contiguous Intervals given a list of numbers: Algorithm of Summarizing Contiguous Intervals

–EOF (The Ultimate Computing & Technology Blog) —