Intervals

The idea

Interval problems give you ranges [start, end]. Almost all start the same way: sort by start (or end), then make a single linear pass deciding how each interval relates to the previous ones. The first decision is which endpoint to sort by — merging sorts by start, greedy scheduling sorts by end.

The overlap test

Two intervals a and b overlap iff a.start <= b.end and b.start <= a.end. Internalize this — it underlies every interval problem.

Merging overlaps

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

Insert Interval is merge with the new interval spliced in (or do it in one pass: emit intervals fully before it, merge those overlapping it, emit the rest). O(n) if already sorted.

Sweep line (event counting)

For “maximum concurrent X” / “how many at once,” convert each interval into +1 at start and −1 at end, sort the events, and track a running count — the peak is the answer:

def max_concurrent(intervals):
    events = []
    for s, e in intervals:
        events.append((s, 1)); events.append((e, -1))   # tie-break: process -1 before +1 if touching = not overlap
    events.sort()
    cur = best = 0
    for _, delta in events:
        cur += delta; best = max(best, cur)
    return best

This generalizes to “minimum meeting rooms,” “car pooling,” “my calendar,” and “skyline” (with heights). Decide the tie-break (does touching count as overlap?) deliberately.

Counting concurrent with a heap

Equivalently, a min-heap of end times gives the room count — pop a room when it frees before the next start:

import heapq
def min_meeting_rooms(intervals):
    intervals.sort(key=lambda x: x[0])
    ends = []
    for s, e in intervals:
        if ends and ends[0] <= s: heapq.heappop(ends)   # a room freed
        heapq.heappush(ends, e)
    return len(ends)

Greedy interval scheduling

To keep the maximum number of non-overlapping intervals (or remove the fewest to make them non-overlapping — “Non-overlapping Intervals”), sort by end time and greedily take each interval that starts after the last taken one ends. The exchange argument proves earliest-finish is optimal (see the greedy primer):

def max_nonoverlapping(intervals):
    intervals.sort(key=lambda x: x[1])           # by END
    count, last_end = 0, float("-inf")
    for s, e in intervals:
        if s >= last_end:
            count += 1; last_end = e
    return count

The family

Merge Intervals, Insert Interval (sort by start) · Non-overlapping Intervals, Minimum Arrows to Burst Balloons (sort by end, greedy) · Meeting Rooms I/II, Car Pooling, My Calendar, The Skyline Problem (sweep line / heap).

Pitfalls

• Sorting by the wrong endpoint — start for merging, end for greedy scheduling.
• Touching boundaries — clarify whether [1,2] and [2,3] overlap; set the comparison (< vs <=) and event tie-break accordingly.
• Mutating shared interval lists — copy if the input must be preserved.

Choosing in an interview

• Combine overlapping ranges → sort by start, merge.
• Peak concurrency / rooms → sweep line or heap of ends.
• Max non-overlapping / min removals → sort by end, greedy.