Blind 75 Visualized

#63 · Intervals

Merge Intervals

Given a list of intervals [start, end], merge all overlapping ones and return the non-overlapping intervals that cover the same ranges.

MediumLeetCode
  • Being examined
  • New / inserted
  • Kept / merged / answer
  • Removed / conflict
  • Untouched
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Sorted array of intervals

After sorting by start, any interval can only overlap the group directly before it: all earlier groups end before the previous group does. So a single left-to-right pass can either extend the last group or start a new one.

Memory layout

An array of [start, end] pairs; the sort is O(n log n) and the pass is O(n). The result can be built in a separate list or in place with a write index.

OperationCost
sortO(n log n)
merge passO(n)

Sweep line over events

Each interval becomes an opening and a closing event. Sorted by time (opens before closes at ties), a counter of open intervals tells when a merged group starts (counter leaves 0) and ends (counter returns to 0).

Memory layout

An array of 2n (time, kind) pairs and a counter.

OperationCost
sort + sweepO(n log n)

Why it fits

  • Overlap is a local property of neighbours once intervals are ordered by start, so ordering turns an all-pairs problem into a single scan.
  • Two intervals overlap when each starts no later than the other ends; the merged interval keeps the earlier start and the later end.
  • Choosing "start ≤ end of the last group" (not "<") merges intervals that only touch, which is what the problem expects.

Why alternatives degrade

Compare every pair repeatedly:
Each merge can create new overlaps, so the scan must restart: O(n³) in the worst case.
Sorting by end time:
It also works if the scan goes right to left, but sorting by end and scanning left to right mis-merges, because an earlier-ending interval can start much later than the one before it.
Hash set of covered points:
Works for small integer coordinates but costs the total length of the intervals, which can be enormous.

Four approaches, from naive to production

1 · beginner

Merge overlapping pairs until none remain

time O(n³)space O(n)

Repeatedly find any two overlapping intervals, replace them with their union, and rescan, until a full pass finds no overlap. Finally sort the result.

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    vector<vector<int>> list = intervals;
    bool changed = true;
    while (changed) {
        changed = false;
        for (size_t i = 0; i < list.size() && !changed; i++) {
            for (size_t j = i + 1; j < list.size(); j++) {
                if (list[i][0] <= list[j][1] && list[j][0] <= list[i][1]) {
                    list[i] = {min(list[i][0], list[j][0]), max(list[i][1], list[j][1])};
                    list.erase(list.begin() + j);
                    changed = true;
                    break;
                }
            }
        }
    }
    sort(list.begin(), list.end());
    return list;
}

Flaws & bottlenecks

  • After every merge the scan starts over, because the new interval can overlap others.
  • Removing from the middle of an array shifts elements.
  • No use is made of order, so many pairs are tested over and over.

Interviewer cross-questions

Why must the scan restart after a merge?

Say: The merged interval is wider than either part, so it may now overlap intervals it did not overlap before. Pairs tested earlier have to be tested again.

How many pair tests can there be?

Say: Up to n²/2 per pass and up to n passes (each pass merges at least one pair), so O(n³).

How does sorting help?

Say: With intervals ordered by start, overlaps can only occur with the immediately preceding group, so one pass is enough.

2 · intermediate

Sort by start, build the result list

time O(n log n)space O(n)

Sort the intervals by start. Walk through them keeping a result list: if the interval starts at or before the end of the last result interval, extend that end; otherwise append the interval.

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    vector<vector<int>> sorted = intervals; sort(sorted.begin(), sorted.end());
    vector<vector<int>> result;
    for (auto& iv : sorted) {
        int start = iv[0], end = iv[1];
        vector<int>* last = result.empty() ? nullptr : &result.back();
        if (last != nullptr && start <= (*last)[1]) (*last)[1] = max((*last)[1], end);
        else result.push_back({start, end});
    }
    return result;
}

Flaws & bottlenecks

  • Allocates a second list for the result.
  • The sort dominates the cost even if the input is almost merged already.
  • Mutating last[1] changes the arrays inside result; copying the input first avoids touching the caller's data.

Interviewer cross-questions

Why is comparing with only the last result interval enough?

Say: Sorted by start, every earlier result interval ends before the last one starts (otherwise it would have been merged), so a new interval cannot reach them.

Should touching intervals ([1,4] and [4,5]) merge?

Say: Yes: they share the point 4, so the condition is start ≤ end, not start < end.

What if intervals are nested, like [1,10] and [2,3]?

Say: Then start ≤ end holds and the new end is max(10, 3) = 10. The max is what keeps a nested interval from shrinking the group.

3 · advanced

Sort, then merge in place

time O(n log n)space O(1) beyond the sort

After sorting keep a write index w to the last finished group. For each following interval either stretch a[w] or move it to a[w + 1]. Finally truncate the array to w + 1 entries.

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    vector<vector<int>> a = intervals; sort(a.begin(), a.end());
    int w = 0;
    for (int i = 1; i < (int)a.size(); i++) {
        if (a[i][0] <= a[w][1]) a[w][1] = max(a[w][1], a[i][1]);
        else a[++w] = a[i];
    }
    a.resize(w + 1);
    return a;
}

Flaws & bottlenecks

  • Overwrites the working array, so the original order is lost (copy first if it matters).
  • The pre-increment in a[++w] = a[i] is compact but easy to misread.
  • Truncating by setting length is language specific (resize, erase or slice elsewhere).

Interviewer cross-questions

Why is overwriting safe?

Say: w never exceeds i, so a[w + 1] is either the cell a[i] itself or a cell whose old contents were already merged and are no longer needed.

How is this different from the list version?

Say: The result lives in the front of the input array, so no second list is allocated; it is the same algorithm with the answer compacted in place.

What changes if the input is already sorted?

Say: Skip the sort: the pass is O(n). Sorted input is common for data coming from an ordered index.

4 · expert

Sweep line over start and end events

time O(n log n)space O(n)

Create an opening event at every start and a closing event at every end, sort the events by time (opens first at ties) and sweep with a counter of open intervals: a merged group starts when the counter leaves 0 and ends when it returns to 0.

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    vector<array<int, 2>> events;
    for (auto& iv : intervals) { events.push_back({iv[0], 0}); events.push_back({iv[1], 1}); }
    sort(events.begin(), events.end());
    vector<vector<int>> result;
    int open = 0, start = 0;
    for (auto& ev : events) {
        int t = ev[0], kind = ev[1];
        if (kind == 0) {
            if (open == 0) start = t;
            open++;
        } else {
            open--;
            if (open == 0) result.push_back({start, t});
        }
    }
    return result;
}

Flaws & bottlenecks

  • Doubles the number of items to sort (2n events).
  • Allocates one small array per event; packing (time, kind) into one number avoids that.
  • The tie-break (opens before closes) is essential and easy to get wrong.

Interviewer cross-questions

Why must opening events come first at the same time?

Say: If a closing event at time 4 were processed before an opening event at time 4, the counter would reach 0 and the group would end, so [1,4] and [4,5] would not merge. Opening first keeps the counter above 0.

Why use this version at all?

Say: The same sweep answers related questions directly: how many intervals overlap at any moment (maximum overlap), or the total covered length. The sorted-interval pass cannot count overlaps.

How can the sort be made cheaper?

Say: Sort two plain arrays of starts and ends instead of event objects, or pack time and kind into one integer so the sort works on numbers.

Synchronized code walkthrough

Showing: Merge overlapping pairs until none remain — shares the player above; click any step to jump.

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    vector<vector<int>> list = intervals;
    bool changed = true;
    while (changed) {
        changed = false;
        for (size_t i = 0; i < list.size() && !changed; i++) {
            for (size_t j = i + 1; j < list.size(); j++) {
                if (list[i][0] <= list[j][1] && list[j][0] <= list[i][1]) {
                    list[i] = {min(list[i][0], list[j][0]), max(list[i][1], list[j][1])};
                    list.erase(list.begin() + j);
                    changed = true;
                    break;
                }
            }
        }
    }
    sort(list.begin(), list.end());
    return list;
}