Problem

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.

Constraints

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

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.

Solution

 1std::vector<std::vector<int>> merge(std::vector<std::vector<int>>& intervals) {
 2    const auto n = intervals.size();
 3    if (n < 2) return intervals;
 4
 5    std::sort(intervals.begin(), intervals.end());  // O(N log N)
 6
 7    std::vector<std::vector<int>> result{intervals.front()};
 8    for (auto i = 1; i < n; ++i) {  // O(N)
 9        const auto& interval = intervals[i];
10        auto& last_end = result.back()[1];
11        if (last_end >= interval[0]) {
12            last_end = std::max(last_end, interval[1]);
13        } else {
14            result.push_back(interval);
15        }
16    }
17
18    return result;
19}

Complexity

• Time: $O(n \log n)$.
• Space: $O(n)$.

See Also

• Merge Intervals