56. Merge Intervals

2020, Oct 26 One min read

1. Description

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

2. Example

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] overlap, 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.

Example 3

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

3. Constraints

1 <= intervals.length <= 10$^{4}$
intervals[i].length == 2
0 <= $start_i$ <= $end_i$ <= 10$^{4}$

4. Solutions

Sort

n = intervals.size()
Time complexity: O(nlogn)
Space complexity: O(logn)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>> intervals) {
        const int n = intervals.size();
        sort(intervals.begin(), intervals.end(), [](const vector<int> &a, const vector<int> &b) {
            return a[0] < b[0];
        });

        vector<vector<int>> ranges;
        int left = intervals[0][0], right = intervals[0][1];
        for (int i = 1; i < n; ++i) {
            if (right < intervals[i][0]) {
                ranges.push_back({left, right});
                left = intervals[i][0];
                right = intervals[i][1];
            } else {
                right = max(right, intervals[i][1]);
            }
        }

        ranges.push_back({left, right});

        return ranges;
    }
};

Search

Tags