lc56

56-Merge Intervals

Description

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.

Exampel 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].

Exampel 2

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

Solution

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        
        sort(intervals.begin(), intervals.end(), [](const auto& x, const auto& y) {
            return x[0] < y[0];
        });

        vector<vector<int>> ans;
        int n = intervals.size();
        vector<int> cur = intervals[0];

        for (int i = 1; i < n; i++) {
            // no overlap
            if (cur[1] < intervals[i][0]) {
                ans.push_back(cur);
                cur = intervals[i];
            } else { // overlap
                cur[1] = max(cur[1], intervals[i][1]);
            }
        }

        ans.push_back(cur);

        return ans;
    }
};