Intervals & Sweep Line

The idea

An interval [start, end] represents a range of time or space. Almost every interval problem starts the same way: sort (by start or by end), then sweep left to right keeping a small amount of state.

Overlap basics

Two intervals [a, b] and [c, d] overlap iff

a <= d and c <= b            (closed intervals; use < for half-open)

Their intersection is [max(a, c), min(b, d)] (valid if start ≤ end). Their union (if overlapping) is [min(a, c), max(b, d)].

Which sort key?

Merge intervals

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []
    for s, e in intervals:
        if merged and s <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], e)   # max: the new one might be contained
        else:
            merged.append([s, e])
    return merged

vector<vector<int>> merge(vector<vector<int>>& iv) {
    sort(iv.begin(), iv.end());
    vector<vector<int>> out;
    for (auto& x : iv) {
        if (!out.empty() && x[0] <= out.back()[1])
            out.back()[1] = max(out.back()[1], x[1]);
        else
            out.push_back(x);
    }
    return out;
}

Insert into a sorted, non-overlapping list

def insert(intervals, new):
    res, i, n = [], 0, len(intervals)
    s, e = new
    while i < n and intervals[i][1] < s:          # entirely before
        res.append(intervals[i]); i += 1
    while i < n and intervals[i][0] <= e:         # overlapping: absorb
        s = min(s, intervals[i][0])
        e = max(e, intervals[i][1])
        i += 1
    res.append([s, e])
    res.extend(intervals[i:])                     # entirely after
    return res

Intersections of two sorted lists

def interval_intersection(A, B):
    i = j = 0
    out = []
    while i < len(A) and j < len(B):
        lo = max(A[i][0], B[j][0])
        hi = min(A[i][1], B[j][1])
        if lo <= hi:
            out.append([lo, hi])
        if A[i][1] < B[j][1]:       # the one that ends first can't intersect anything else
            i += 1
        else:
            j += 1
    return out

Maximum concurrency: the sweep line

Turn each interval into two events: +1 at start, −1 at end. Sort events; the running sum is the number of active intervals at each point.

def min_meeting_rooms(intervals):
    events = []
    for s, e in intervals:
        events.append((s, 1))
        events.append((e, -1))
    events.sort()        # at equal times, -1 sorts before +1 → a meeting ending at t frees the room for one starting at t
    cur = best = 0
    for _, delta in events:
        cur += delta
        best = max(best, cur)
    return best

int minMeetingRooms(vector<vector<int>>& iv) {
    vector<pair<int, int>> ev;
    for (auto& x : iv) { ev.push_back({x[0], 1}); ev.push_back({x[1], -1}); }
    sort(ev.begin(), ev.end());
    int cur = 0, best = 0;
    for (auto& [t, d] : ev) { cur += d; best = max(best, cur); }
    return best;
}

Heap alternative

Sort by start; keep a min-heap of end times of rooms in use. If the earliest-ending room is free, reuse it.

import heapq

def min_meeting_rooms_heap(intervals):
    intervals.sort()
    ends = []
    for s, e in intervals:
        if ends and ends[0] <= s:
            heapq.heapreplace(ends, e)    # reuse the room that frees up first
        else:
            heapq.heappush(ends, e)
    return len(ends)

The heap version also tells you which room each meeting goes to, which the counting version can't.

Sweep with a difference array

When coordinates are small integers, skip sorting: diff[start] += 1; diff[end] -= 1, then prefix-sum. See Prefix Sums.

Dynamic intervals: sorted containers

For online insertion (My Calendar, Range Module, Count Integers in Intervals), keep intervals in a balanced BST keyed by start and check/merge with neighbours.

// My Calendar I: book [s, e) if it doesn't overlap
map<int, int> cal;   // start -> end
bool book(int s, int e) {
    auto it = cal.lower_bound(s);                 // first start >= s
    if (it != cal.end() && it->first < e) return false;
    if (it != cal.begin() && prev(it)->second > s) return false;
    cal[s] = e;
    return true;
}

from sortedcontainers import SortedList   # available on LeetCode

class MyCalendar:
    def __init__(self):
        self.starts = SortedList()
        self.end_of = {}
    def book(self, s, e):
        i = self.starts.bisect_left(s)
        if i < len(self.starts) and self.starts[i] < e:
            return False
        if i > 0 and self.end_of[self.starts[i - 1]] > s:
            return False
        self.starts.add(s); self.end_of[s] = e
        return True

The skyline problem (sweep + heap)

Process building edges by x. At a left edge, add the height; at a right edge, remove it. The skyline changes whenever the current max height changes. Use a max-heap with lazy deletion (pop heights whose building has already ended).

import heapq

def get_skyline(buildings):
    events = sorted([(l, -h, r) for l, r, h in buildings] + [(r, 0, 0) for _, r, _ in buildings])
    res, heap = [], [(0, float("inf"))]          # (-height, end)
    for x, neg_h, r in events:
        while heap[0][1] <= x:                    # lazily drop ended buildings
            heapq.heappop(heap)
        if neg_h:
            heapq.heappush(heap, (neg_h, r))
        top = -heap[0][0]
        if not res or res[-1][1] != top:
            res.append([x, top])
    return res

Common mistakes

• Forgetting max() when merging (a contained interval would shrink the end).
• Wrong tie-breaking in sweep events (end before start or not, depending on whether touching overlaps).
• Mutating input intervals that the caller still uses.
• Sorting by start when the greedy needs end (or vice versa).