Merge Intervals

Introduction

Intervals are everywhere in production software. They represent calendar events, string spans, segments on a number line, TCP flows, reservations, cache lifetimes, query ranges, lock holds. And yet the genre of interview problems around them reduces, almost entirely, to a single technique: sort by an endpoint, then walk the list once. Merge Intervals is the chapter that teaches it.

This problem shows up so reliably at Google, Meta, and Amazon that recruiters joke about it. Its interview utility is not that it is hard — the final algorithm is a dozen lines — but that it discriminates cleanly between candidates who guess and candidates who reason. A candidate who sorts by start and walks once is strong. One who also articulates why sorting by start is the correct choice, and why one pass after sorting is sufficient, is stronger still. And one who can then solve the Meeting Rooms variant with either a sweep or a heap, each time explaining the tradeoff, is the candidate we hire.

Sort the boundaries, sweep once. Two phrases that solve the majority of the interval problems you will ever see.

What the interviewer is actually testing

1. Do you reach for sorting on first principles? Unsorted intervals force $O(n^2)$. Sorted intervals collapse to $O(n)$. Recognizing this is the entire game.
2. Can you state a precise overlap condition? Most candidates mumble a case-by-case list. Strong candidates write one inequality.
3. Can you prove your one-pass sweep is correct? The “I just compare to the back of the output” line is not a proof. An invariant is.
4. Can you extend cleanly? The Meeting Rooms variant, the insert-interval variant, the non-overlapping-intervals variant — all should feel like variations on the same theme once the first problem is solved.

Problem statement

Clarifying questions — and why each one matters

The overlap condition — write this once, use it forever

Most candidates get asked “when do two intervals overlap?” at some point. The mumbled answer goes: “well, either $a$ is inside $b$, or $b$ is inside $a$, or $a$‘s start is inside $b$, or $b$‘s start is inside $a$…”. Four cases, bug-prone.

The clean answer is one inequality. Two intervals $a = (a_s, a_e)$ and $b = (b_s, b_e)$ overlap iff

$\max(a_s, b_s) \le \min(a_e, b_e).$

Carry this formula with you. It’s the overlap test for every interval problem in the book.

Discussion

#include <algorithm>
#include <vector>

struct Interval {
    int start;
    int end;
};

// Two intervals overlap iff max(a.start, b.start) <= min(a.end, b.end).
static bool overlaps(const Interval& a, const Interval& b) {
    return std::max(a.start, b.start) <= std::min(a.end, b.end);
}

static Interval fuse(const Interval& a, const Interval& b) {
    return { std::min(a.start, b.start), std::max(a.end, b.end) };
}

std::vector<Interval> merge(const std::vector<Interval>& in) {
    const int n = static_cast<int>(in.size());
    std::vector<bool> absorbed(n, false);
    std::vector<Interval> out;

    for (int i = 0; i < n; ++i) {
        if (absorbed[i]) continue;
        Interval cur = in[i];
        // Keep scanning the whole list until no more absorbs happen.
        // A single pass is not enough: newly-fused intervals may overlap
        // ones already skipped in this iteration.
        bool changed = true;
        while (changed) {
            changed = false;
            for (int j = 0; j < n; ++j) {
                if (j == i || absorbed[j]) continue;
                if (overlaps(cur, in[j])) {
                    cur = fuse(cur, in[j]);
                    absorbed[j] = true;
                    changed = true;
                }
            }
        }
        out.push_back(cur);
    }
    return out;
}

sort I by start ascending
out = [I[0]]
for iv in I[1..]:
if iv.start <= out.last.end:
  out.last.end = max(out.last.end, iv.end)
else:
  out.append(iv)
return out

#include <algorithm>
#include <vector>

struct Interval {
    int start;
    int end;
};

// O(n log n) time (from the sort), O(n) space for the output.
// Handles touching intervals as overlapping: (1,3) and (3,5) merge into (1,5).
// If the desired convention is strict overlap only, change `<=` to `<`.
std::vector<Interval> merge(std::vector<Interval> in) {
    if (in.empty()) return {};

    std::sort(in.begin(), in.end(),
              [](const Interval& a, const Interval& b) {
                  return a.start < b.start;
              });

    std::vector<Interval> out;
    out.reserve(in.size());
    out.push_back(in.front());

    for (size_t i = 1; i < in.size(); ++i) {
        Interval& back = out.back();
        const Interval& next = in[i];

        // Sorted by start, so the only way to overlap is
        // for next.start to fall inside [back.start, back.end].
        if (next.start <= back.end) {
            back.end = std::max(back.end, next.end);
        } else {
            out.push_back(next);
        }
    }
    return out;
}

Approach comparison

Related — How many meeting rooms?

A nearly-guaranteed follow-up: given a list of meetings, how many rooms do we need so that no two overlapping meetings share a room?

#include <algorithm>
#include <vector>

struct Interval {
    int start;
    int end;
};

// Sort starts and ends independently. Walk them with two pointers.
// A start event before the next end means we need another room.
// Otherwise we can reuse a room that just freed up.
int minMeetingRooms(const std::vector<Interval>& meetings) {
    const size_t n = meetings.size();
    if (n == 0) return 0;

    std::vector<int> starts, ends;
    starts.reserve(n);
    ends.reserve(n);
    for (const auto& m : meetings) {
        starts.push_back(m.start);
        ends.push_back(m.end);
    }

    std::sort(starts.begin(), starts.end());
    std::sort(ends.begin(), ends.end());

    int rooms = 0;
    int peak  = 0;
    size_t e  = 0;

    for (size_t s = 0; s < n; ++s) {
        while (e < n && ends[e] <= starts[s]) {
            --rooms;
            ++e;
        }
        ++rooms;
        peak = std::max(peak, rooms);
    }
    return peak;
}

#include <algorithm>
#include <queue>
#include <vector>

struct Interval {
    int start;
    int end;
};

// Min-heap of end-times, sorted starts.
// For each meeting (in order of start time): if the earliest-ending room
// has freed up by `start`, reuse it; otherwise open a new room.
// Same O(n log n) complexity as the sweep approach, arguably clearer code.
int minMeetingRooms(std::vector<Interval> meetings) {
    if (meetings.empty()) return 0;

    std::sort(meetings.begin(), meetings.end(),
              [](const Interval& a, const Interval& b) {
                  return a.start < b.start;
              });

    std::priority_queue<int, std::vector<int>, std::greater<int>> endTimes;

    for (const auto& m : meetings) {
        if (!endTimes.empty() && endTimes.top() <= m.start) {
            endTimes.pop();           // free the earliest-finishing room
        }
        endTimes.push(m.end);         // assign m to a room (new or reused)
    }
    return static_cast<int>(endTimes.size());
}

Edge cases across both problems

Follow-ups to anticipate

Pattern recognition — the sweep-line family

The pattern you learned here is the sweep line. It generalizes to nearly every problem where events happen over a 1D axis and you need to know something about “what is happening at time $t$”. The idea:

1. Extract events (endpoints).
2. Sort events by time.
3. Walk events in time order, maintaining running state.

Problems that belong to this family:

• Insert Interval, Non-overlapping Intervals, Erase Overlap Intervals — direct applications.
• The Skyline Problem — sweep x-coordinates with a heap of live heights.
• Minimum Arrows to Burst Balloons — greedy shooting with a sorted-end-time sweep.
• Employee Free Time — merge intervals across multiple sorted lists (use a min-heap of starts).
• Maximum Population Year — difference array or sweep to find peak concurrency.
• Calendar scheduling (Calendar I, II, III) — all sweep variants.

Once you see the shape — “events on a number line, need a property of the running state” — you reach for sort + sweep on reflex.

What to say out loud — the delivery script

1. Restate the problem. “I’m given a list of intervals, possibly overlapping; I need to return the list of their non-overlapping unions.”
2. Ask the three questions. Sorted? Touching semantics? In-place?
3. State the overlap formula. “Two intervals overlap iff $\max(a_s, b_s) \le \min(a_e, b_e)$.”
4. Brute force as a baseline. “I could scan the list $n$ times, greedily absorbing — that’s $O(n^2)$.”
5. Propose the sort. “But if I sort by start, any interval that doesn’t overlap the previous one can’t overlap any earlier one either, so I only need to compare each interval to the back of the output list. That’s $O(n \log n)$.”
6. Write the code. A dozen lines.
7. Walk an example. Trace the algorithm on $[(3,7), (1,5), (6,8), (4,6)]$.
8. State the invariant. “After each step, the output correctly merges the prefix of the sorted input.”
9. Call out the touching semantics and other edge cases.
10. Gesture at follow-ups. “If we needed to answer ‘how many meeting rooms’, I’d switch to a sweep of endpoints or a min-heap of end times.”
11. Summarize. “I’d ship the sort-then-merge version.”

Summary

Merge Intervals is the sweep-line family’s hello-world. Nail the overlap formula, internalize the sort-by-start then compare-to-back-of-output pattern, and state the invariant that makes it correct. Once you have, the entire family — insert, remove, intersection, gaps, meeting rooms, skyline — becomes small variations on a theme you already understand.

The skill you’re actually practicing here, the one that transfers to dozens of problems, is “extract boundary events, sort them, walk once”. Internalize that and half of the interval problems in your interview pack reduce to thirty lines of code.