56. Merge Intervals

Posted on Edited on In

56. Merge Intervals

Description

Given an array of intervalswhere intervals[i] = [start<sub>i</sub>, end<sub>i</sub>], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

1
2
3
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:

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

Constraints:

  • 1 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= start<sub>i</sub> <= end<sub>i</sub> <= 10^4

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> res;
        ranges::sort(intervals);
        int n = intervals.size();
        for (int i = 0; i < n; ) {
            int start = intervals[i][0], end = intervals[i][1];
            i++;
            while (i < n && intervals[i][0] <= end) {
                end = max(end, intervals[i][1]);
                i++;
            }
            res.push_back({start, end});
        }
        return res;
    }
};