Intervals — merge, insert, schedule

An interval is just a [start, end] pair, and almost every interval problem is secretly the same question: "which of these ranges touch each other?" The universal first move is sort by start time — once sorted, any overlap can only be with a neighbor, so a single left-to-right pass settles everything. The overlap test is one line: [a,b] and [c,d] overlap when a <= d and c <= b — i.e. they miss only if one ends before the other starts.

The vocabulary, defined once

Before the patterns, pin down every word so nothing later is a mystery. Each term here is something interviewers will say out loud, so being able to name them back is half the battle.

• Interval — an ordered pair [start, end] with start <= end, naming a continuous stretch on a number line (a time window, a page range, a segment). The two numbers are its endpoints; the left one is the start (or "open"/"arrival") and the right one is the end (or "close"/"departure").
• Overlap — two intervals overlap when they share at least one point. Formally, [a,b] and [c,d] overlap exactly when a <= d and c <= b. The cleaner way to remember it: they do not overlap only if one finishes strictly before the other starts (b < c or d < a); negate that and you get the overlap condition.
• Sort-by-start — ordering the whole list ascending by the start value ([1,9],[2,3],[8,10] sorts to [1,9],[2,3],[8,10]). This is the setup move for merge and insert: it guarantees that as you scan left to right, every interval begins no earlier than the one before, so any overlap must be with what you most recently kept.
• The sweep / merge technique — "sweep" just means walking through the sorted items once, left to right, carrying a small amount of running state (here, the last interval you kept). You never go backwards. That single forward pass is what turns a quadratic "compare everything to everything" idea into a linear scan.
• Sweep line / events — a generalization of the sweep where you don't walk the intervals themselves but a sorted list of events on the timeline: a +1 event at each start, a -1 event at each end. Processing events in time order lets you track "how many intervals are active right now" without ever comparing pairs.
• Min-heap of ends — a priority queue that always hands back its smallest element first. For scheduling, we keep the end times of meetings currently using a room in a min-heap so the earliest-finishing room is always one peek away. ("Min-resources" / "min-rooms" is the pattern of finding the fewest concurrent resources needed to cover everything — see below.)

On-ramp: sort first, then sweep

If you remember only five words from this lesson, make them "sort first, then sweep." Almost every interval task collapses to those two phases. Sort imposes an order so neighbors are the only things that can interact. Sweep walks that order once, keeping a tiny bit of state, and decides each item by comparing it to what came just before. The only thing that changes between problems is (a) which key you sort on (start vs. end) and (b) what state you carry during the sweep (the last kept interval, a running count, or a heap of end times). Get those two choices right and the code writes itself.

The overlap test, spelled out

In the merge code below you'll see the condition written as s <= out[-1][1] — "my start is at or before the last kept end." That's a special case of the general overlap test that works because we sorted by start: once sorted, the new interval's start is already >= the previous start, so we only need to check the other half of the condition. The full, order-independent test is a <= d and c <= b for [a,b] vs [c,d]. Read it as two simultaneous demands: the first interval must start no later than the second ends, and the second must start no later than the first ends. If either demand fails, there's a clean gap between them.

def merge(intervals):
    intervals.sort(key=lambda x: x[0])   # sort by START
    out = []
    for s, e in intervals:
        if out and s <= out[-1][1]:        # overlaps prev
            out[-1][1] = max(out[-1][1], e)
        else:
            out.append([s, e])
    return out

function merge(iv: number[][]): number[][] {
  iv.sort((a, b) => a[0] - b[0]);
  const out: number[][] = [];
  for (const [s, e] of iv) {
    const last = out[out.length - 1];
    if (last && s <= last[1]) last[1] = Math.max(last[1], e);
    else out.push([s, e]);
  }
  return out;
}

One subtlety the trace above quietly handled: when we extend the last interval we take max(out[-1][1], e), not just e. That matters for a swallowed interval like [1,9] followed by [2,3] — the new end 3 is smaller, so blindly writing e would shrink a range that already covered it. max keeps the farther-right edge and absorbs the smaller interval entirely.

Insert into a sorted interval list

The insert variant gives you an already-sorted, non-overlapping list plus one new interval, and asks for the merged result. Because the list is already sorted you can skip the sort entirely and walk it in three phases — think of them as three buckets relative to the new interval [ns, ne]:

• Before — every interval that ends strictly before the new one starts (end < ns). These can't touch it; copy them over unchanged.
• Overlap — every interval that touches the new one (start <= ne and end >= ns). Don't emit these individually; instead grow [ns, ne] to swallow them by taking ns = min(ns, start) and ne = max(ne, end). After the overlap run, push the single grown interval once.
• After — every interval that starts strictly after the new one ends (start > ne). Copy the rest over unchanged.

def insert(intervals, new):
    ns, ne = new
    out, i, n = [], 0, len(intervals)
    # 1) before: ends before new starts
    while i < n and intervals[i][1] < ns:
        out.append(intervals[i]); i += 1
    # 2) overlap: grow [ns, ne] to swallow them
    while i < n and intervals[i][0] <= ne:
        ns = min(ns, intervals[i][0])
        ne = max(ne, intervals[i][1]); i += 1
    out.append([ns, ne])
    # 3) after: copy the rest
    while i < n:
        out.append(intervals[i]); i += 1
    return out

function insert(iv: number[][], nw: number[]): number[][] {
  let [ns, ne] = nw;
  const out: number[][] = [];
  let i = 0, n = iv.length;
  while (i < n && iv[i][1] < ns) out.push(iv[i++]);   // before
  while (i < n && iv[i][0] <= ne) {                  // overlap
    ns = Math.min(ns, iv[i][0]);
    ne = Math.max(ne, iv[i][1]); i++;
  }
  out.push([ns, ne]);
  while (i < n) out.push(iv[i++]);                  // after
  return out;
}

Minimum meeting rooms (min-resources)

The min-rooms / min-resources pattern asks: given a pile of meetings, what is the fewest number of rooms (servers, lanes, platforms) you need so that no two overlapping meetings share one? The answer is exactly the maximum number of meetings that are ever in progress at the same instant — the peak concurrency. There are two clean ways to compute it, and both reduce to "sort, then sweep."

• Min-heap of end times. Sort meetings by start. Walk them in order, keeping a min-heap of the end times of meetings currently occupying a room. For each new meeting, if the earliest-ending room (the heap's smallest end) finishes at or before this meeting's start, that room is free — pop it and reuse it. Either way, push the new meeting's end. The heap's largest size reached is the room count. Cost: O(n log n).
• Sweep line of events. Don't track rooms at all — track the timeline (this is the box just below). Emit +1 at every start and -1 at every end, sort events by time, sweep, and report the peak running sum.

import heapq
def min_rooms(meetings):
    meetings.sort(key=lambda x: x[0])   # sort by START
    heap = []                            # end times of busy rooms
    for s, e in meetings:
        if heap and heap[0] <= s:       # earliest room is free
            heapq.heappop(heap)
        heapq.heappush(heap, e)          # occupy a room until e
    return len(heap)               # peak concurrency = rooms

// MinHeap is a standard min-priority-queue (peek = smallest)
function minRooms(m: number[][]): number {
  m.sort((a, b) => a[0] - b[0]);   // sort by START
  const heap = new MinHeap();          // end times of busy rooms
  for (const [s, e] of m) {
    if (heap.size && heap.peek() <= s) heap.pop();  // free a room
    heap.push(e);                     // occupy until e
  }
  return heap.size;                 // peak concurrency = rooms
}

Recognition signals & pitfalls

In an interview the hard part is rarely the code — it's noticing this is an interval problem and choosing the right sort key. Use these tells, then sidestep the classic traps.

Implement the sort-then-sweep merge — run it live: