Merge Intervals medium

Problem Statement

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.

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] overlaps, 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.

Steps

1. Sort the intervals: Sort the intervals based on their start times. This ensures that we process overlapping intervals consecutively.

2. Initialize the merged intervals: Create a vector to store the merged intervals. Add the first interval from the sorted list to the merged vector.

3. Iterate and merge: Iterate through the sorted intervals starting from the second interval. For each interval:

   • If the current interval overlaps with the last interval in merged, merge them by updating the end time of the last interval in merged to the maximum of the current interval's end time and the last interval's end time.
   • If the current interval does not overlap, add it to the merged vector.

4. Return the merged intervals: Return the merged vector containing the non-overlapping intervals.

Explanation

The key idea is to sort the intervals by their start times. This allows us to process them sequentially and efficiently identify overlapping intervals. Overlapping intervals will always be adjacent after sorting. We merge them by taking the maximum of their end times. This guarantees that we cover all the points within the overlapping intervals.

Code

#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if (intervals.empty()) return {};

    // Sort intervals by start time
    sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    });

    vector<vector<int>> merged;
    merged.push_back(intervals[0]); // Add the first interval

    for (size_t i = 1; i < intervals.size(); ++i) {
        vector<int>& current = intervals[i];
        vector<int>& last = merged.back();

        // Check for overlap: If current start is <= last end
        if (current[0] <= last[1]) {
            // Merge by updating the end of the last interval
            last[1] = max(last[1], current[1]);
        } else {
            // No overlap, add the current interval
            merged.push_back(current);
        }
    }

    return merged;
}

Complexity

• Time Complexity: O(N log N), dominated by the sorting step. The iteration through the sorted intervals takes linear time.
• Space Complexity: O(N) in the worst case, if no intervals are merged (all intervals are non-overlapping). The merged vector could potentially store all the input intervals. In the best case (all intervals merge), space complexity is O(1).