MEDIUM

Merge Intervals

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.

Example

Input:

intervals = [[1,3],[2,6],[8,10],[15,18]]

Output:

[[1,6],[8,10],[15,18]]

Explanation:
Intervals [1,3] and [2,6] overlap, so they are merged into [1,6].

Constraints

1 ≤ intervals.length ≤ 10⁴
intervals[i].length == 2
0 ≤ start_i ≤ end_i ≤ 10⁴

Solution: Sorting

Time Complexity: O(n log n)
Space Complexity: O(n)

C++

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& i) {
        vector<vector<int>> ans;
        sort(i.begin(), i.end());
        for (auto& c : i) {
            if (ans.empty() || ans.back()[1] < c[0]) ans.push_back(c); // merge intervals
            else ans.back()[1] = max(ans.back()[1], c[1]); // add new intervals
        }
        return ans;
    }
};