Back to solutions

Merge Intervals

MediumArrays

Merge all overlapping intervals.

Open problem
Constraints
  • 1 <= n <= 10^4
  • start <= end

Sort then sweep

Time O(n log n)Space O(n)

Sort the intervals by start. Walk through them keeping the last merged interval; if the current interval starts at or before the last one's end, they overlap, so extend the last end. Otherwise the current interval begins a new block.

Key terms
interval:
A [start, end] range on the number line.
overlap:
Two intervals overlap when one starts at or before the other ends.
vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> res;
    for (auto& iv : intervals) {
        if (!res.empty() && iv[0] <= res.back()[1])
            res.back()[1] = max(res.back()[1], iv[1]);
        else res.push_back(iv);
    }
    return res;
}
Step by step
  1. Sort intervals by their start value.
  2. Start the result with the first interval.
  3. For each next interval, if its start <= the last result's end, extend that end to the max of the two.
  4. Otherwise append it as a new interval. Return the result list.