Merge Intervals

Link

Description

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

Constraints:

• 1 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= start_i <= end_i <= 10^4

Solution

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> res;
        int n = intervals.size();
        if (!n) return res;

        sort(intervals.begin(), intervals.end(), [](vector<int>& lhs, vector<int>& rhs) { return lhs[0] < rhs[0]; });
        res.push_back(intervals[0]);

        for (int i = 1; i < n; i++) {
            auto backVec = res.back();
            if (intervals[i][0] > backVec[1]) {
                res.push_back(intervals[i]);
            } else {
                res.back()[1] = max(res.back()[1], intervals[i][1]);
            }
        }
        return res;
    }
};

• Time complexity: \(O(n\log n)\);
• Space complexity: \(O(n)\).

Another way of writing:

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());

        vector<vector<int>> res;
        int left = intervals[0][0], right = intervals[0][1];
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] > right) {
                res.push_back({left, right});
                left = intervals[i][0], right = intervals[i][1];
            } else {
                right = max(right, intervals[i][1]);
            }
        }
        res.push_back({left, right});

        return res;
    }
};

Algorithm Explanation:

1. Sorting the Intervals:
   • The first step involves sorting the intervals array. The sort() function, by default, sorts the array in ascending order based on the first element of each interval. If the first elements are equal, it sorts based on the second element. This step is crucial as it arranges the intervals in a sequence where potentially overlapping intervals are placed next to each other, simplifying the merging process.
2. Initializing Variables:
   • Two variables left and right are initialized with the first interval's start and end points, respectively. These variables are used to track the current interval being formed or merged.
3. Iterating Through the Intervals:
   • The algorithm iterates through the intervals starting from the second interval. For each interval, it checks if the current interval's start point (intervals[i][0]) is greater than the right of the interval being formed. If true, this indicates that the current interval does not overlap with the interval being formed, and hence, the formed interval is pushed into the result array res. The left and right are then updated to the current interval's values, starting the formation of a new interval.
   • If the current interval's start is not greater than right, it means the current interval overlaps with the interval being formed. The right is then updated to the maximum of the current right and the end point of the current interval (intervals[i][1]), effectively merging the intervals.
4. Final Interval Addition:
   • After the loop, the last formed or merged interval is added to the result array res. This step is necessary because the last interval formed by the iteration process has not yet been added to the result array.

Another way of writing:

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());

        vector<vector<int>> res;
        for (const auto& interval : intervals) {
            if (res.empty() || interval[0] > res.back()[1]) {
                res.push_back(interval);
            } else {
                res.back()[1] = max(res.back()[1], interval[1]);
            }
        }

        return res;
    }
};