Merge Intervals

Practice here

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.

Linear scan#

• Intuition: After sorting intervals by start time, any two overlapping intervals must be adjacent in the sorted order. A single left-to-right sweep can therefore process all merges without ever revisiting earlier intervals.
• Mechanics: The result list is seeded with the first interval. For each subsequent interval, if its start is <= the last merged interval's end, the two overlap — extend the last interval's end to the max of both ends. Otherwise, no overlap; push the current interval as a new entry and advance the write pointer.
• Trade-off: Sorting takes O(n log n) and the scan is O(n). An extra output array of size O(n) is used. The in-place variant below eliminates the auxiliary array at the cost of slightly more bookkeeping.

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> mergedIntervals;

        sort(intervals.begin(), intervals.end());

        mergedIntervals.push_back(intervals[0]);
        int idx=0;
        for(int i=1;i<intervals.size();i++){
            if(intervals[i][0] <= mergedIntervals[idx][1]){
                mergedIntervals[idx][1] = max(mergedIntervals[idx][1], intervals[i][1]);
            }else{
                mergedIntervals.push_back(intervals[i]);
                idx++;
            }
        }
        return mergedIntervals;
    }
};

Time Complexity: O(nlog n) + O(n)

Space Complexity: O(n)

Better approach: No extra Space#

After sorting intervals by start time, all overlapping intervals will appear next to each other. So we can scan left to right once and merge on the fly. Think of it as painting a timeline:

• Start with the first interval → this is your current painted segment.
• Look at the next interval:
  • If it overlaps → extend your painted segment (merge).
  • If it doesn’t → lock the previous segment and start a new one.

Why use idx -> write pointer?

• We are trying to merge in-place, not using a separate result vector.
• idx always points to the last merged interval in intervals[0..idx]

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

        int idx = 0;
        for(int i=1;i<intervals.size();i++)
        {
            if(intervals[i][0] <= intervals[idx][1]){
                intervals[idx][1] = max(intervals[idx][1], intervals[i][1]);
            } else{
                idx++;
                intervals[idx] = intervals[i];
            }
        }
        intervals.resize(idx+1);
        return intervals;
    }
};

Time Complexity: O(nlog n) + O(n)

Space Complexity: O(1)