Merge Intervals works by comparing intervals to each other. That is the right tool when you need to combine them. But when the question is “how many overlap at the busiest moment?”, comparing pairs is the wrong frame — and $O(n^2)$.

The sweep line reframes it. Stop thinking about intervals as objects and think about the moments they change something:

An interval [start, end)[start, end) is really two events: +1+1 at startstart and -1-1 at endend.

Sort all the events by time, walk through them keeping a running total, and that total is the number of active intervals at every instant. The maximum it reaches is your answer.

What you’ll learn

• The +1 / -1+1 / -1 event transform, and why sorting events beats comparing intervals.
• The tie-breaking rule at a shared timestamp — which decides whether touching intervals count as overlapping.
• Inclusive vs. half-open endpoints, and the end + 1end + 1 fix.
• When a min-heap of end times is the better shape than events.
• Three real LeetCode problems solved in the browser: 1094, 2406, 253.

The cue

The template

def max_overlap(intervals):
    """Peak number of simultaneously active [start, end) intervals."""
    events = []
    for start, end in intervals:
        events.append((start, 1))     # one more active from here
        events.append((end, -1))      # one fewer from here
 
    events.sort()                     # by time; -1 before +1 at equal times
 
    active = best = 0
    for _time, delta in events:
        active += delta
        best = max(best, active)
    return best
 
 
print(max_overlap([[0, 30], [5, 10], [15, 20]]))   # 2
print(max_overlap([[7, 10], [2, 4]]))              # 1

def max_overlap(intervals):
    """Peak number of simultaneously active [start, end) intervals."""
    events = []
    for start, end in intervals:
        events.append((start, 1))     # one more active from here
        events.append((end, -1))      # one fewer from here
 
    events.sort()                     # by time; -1 before +1 at equal times
 
    active = best = 0
    for _time, delta in events:
        active += delta
        best = max(best, active)
    return best
 
 
print(max_overlap([[0, 30], [5, 10], [15, 20]]))   # 2
print(max_overlap([[7, 10], [2, 4]]))              # 1

$O(n \log n)$ for the sort, then a single $O(n)$ pass. Space $O(n)$ for the events.

The heap alternative

For “minimum rooms” there is a second formulation that some find more intuitive: sort intervals by start, and keep a min-heap of end times of the currently-occupied rooms.

import heapq
 
 
def min_rooms(intervals):
    if not intervals:
        return 0
    intervals.sort()                       # by start time
    ends = []                              # min-heap of end times in use
    for start, end in intervals:
        if ends and ends[0] <= start:      # earliest-finishing room is free
            heapq.heappop(ends)            # reuse it
        heapq.heappush(ends, end)
    return len(ends)                       # rooms ever needed at once
 
 
print(min_rooms([[0, 30], [5, 10], [15, 20]]))   # 2

import heapq
 
 
def min_rooms(intervals):
    if not intervals:
        return 0
    intervals.sort()                       # by start time
    ends = []                              # min-heap of end times in use
    for start, end in intervals:
        if ends and ends[0] <= start:      # earliest-finishing room is free
            heapq.heappop(ends)            # reuse it
        heapq.heappush(ends, end)
    return len(ends)                       # rooms ever needed at once
 
 
print(min_rooms([[0, 30], [5, 10], [15, 20]]))   # 2

Same complexity. The event version generalises better (it handles weights, as in LC 1094, and produces the full profile); the heap version tells you which resource is being reused, which matters if rooms have identities.

The variant map

Practice — real LeetCode problems

LC 1094 — Car Pooling · Medium

Problem. A car with capacitycapacity empty seats drives east only. Given trips[i] = [numPassengers, from, to]trips[i] = [numPassengers, from, to], return TrueTrue if it is possible to pick up and drop off all passengers without ever exceeding capacity.

Constraints. 1 <= len(trips) <= 10001 <= len(trips) <= 1000, 1 <= numPassengers <= 1001 <= numPassengers <= 100, 0 <= from < to <= 10000 <= from < to <= 1000, 1 <= capacity <= 10^51 <= capacity <= 10^5.

Examples. trips = [[2,1,5],[3,3,7]], capacity = 4trips = [[2,1,5],[3,3,7]], capacity = 4 gives FalseFalse · same trips with capacity = 5capacity = 5 gives TrueTrue

delta = [0] * 1001
for num, start, end in trips:
    delta[start] += num
    delta[end] -= num
onboard = 0
for d in delta:
    onboard += d
    if onboard > capacity:
        return False
return True

delta = [0] * 1001
for num, start, end in trips:
    delta[start] += num
    delta[end] -= num
onboard = 0
for d in delta:
    onboard += d
    if onboard > capacity:
        return False
return True

LC 2406 — Divide Intervals Into Minimum Number of Groups · Medium

Problem. Given intervals[i] = [left, right]intervals[i] = [left, right] (both endpoints inclusive), split them into the minimum number of groups such that no two intervals in the same group intersect. Return that minimum.

Constraints. 1 <= len(intervals) <= 10^51 <= len(intervals) <= 10^5, 1 <= left <= right <= 10^61 <= left <= right <= 10^6.

Examples. [[5,10],[6,8],[1,5],[2,3],[1,10]][[5,10],[6,8],[1,5],[2,3],[1,10]] gives 33 · [[1,3],[5,6],[8,10],[11,13]][[1,3],[5,6],[8,10],[11,13]] gives 11

LC 253 — Meeting Rooms II · Medium · Premium

Problem. Given meeting time intervals [start, end)[start, end), return the minimum number of conference rooms required.

Examples. [[0,30],[5,10],[15,20]][[0,30],[5,10],[15,20]] gives 22 · [[7,10],[2,4]][[7,10],[2,4]] gives 11

LeetCode problem set

Interview follow-ups

Edge-case checklist

• Empty input — must return 00; the event version handles it, the heap version needs a guard.
• Single interval — answer 11.
• Touching intervals — [[1,5],[5,10]][[1,5],[5,10]]; the case that exposes the endpoint convention. Half-open gives 11, inclusive gives 22.
• Fully nested intervals — [[1,10],[2,9],[3,8]][[1,10],[2,9],[3,8]] gives 33; overlap is not just about crossing edges.
• Identical intervals — nn copies overlap nn times.
• Zero-length interval — [[1,1]][[1,1]]; sane under inclusive endpoints, degenerate under half-open.
• All disjoint — answer 11, verifying you take a maximum rather than a total.
• Unsorted input — always sort; never assume the input is ordered.

Recap

• Turn each interval into two events: +1+1 at start, -1-1 at end. Sort, scan, keep a running total — that total is the live overlap.
• Minimum rooms/groups = peak overlap. Be ready to prove both bounds.
• The tie-break is the pattern’s one real subtlety. Half-open intervals work for free because (t, -1)(t, -1) sorts before (t, 1)(t, 1). Inclusive endpoints need end + 1end + 1.
• Events carry weights just as easily as ±1±1 (LC 1094).
• When coordinates are small and bounded, a difference array skips the sort entirely — $O(n + \text{range})$.
• A min-heap of end times is the equivalent formulation, and is better when you need to know which resource is reused.
• Merging intervals outputs intervals; sweeping outputs a count. Choose by what the answer looks like.

Next: Greedy Interval Scheduling — why sorting by end time is the right move when you want to keep as many intervals as possible.