Skip to main content

Merge Intervals

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.

Solution Approach​

Click - to see solution code
class Solution {
   public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> ans;
        sort(intervals.begin(), intervals.end());
        int front = intervals[0][0];
        int back = intervals[0][1];

        for (int i = 1; i < intervals.size(); i++) {
            int left = intervals[i][0];
            int right = intervals[i][1];
            if (left <= back && front <= right) {
                front = min(left, front);
                back = max(back, right);
            } else {
                ans.push_back({front, back});
                front = left;
                back = right;
            }
        }
        ans.push_back({front, back});

        return ans;
    }
};