Counting Overlaps with a Sweep Line

EditorialUpdated Oct 25, 2026

Every meeting has to happen

Interval Scheduling: Sort by End Time kept the most meetings in one room. Now nobody gets turned away: every meeting happens, and the question is how many rooms that takes.

Picture a line sweeping across the day. Wherever it is, the meetings it crosses each need their own room at that moment. So the day needs at least as many rooms as the most meetings the line ever crosses, and it turns out that many is also enough. The answer is the most meetings in progress at one moment.

The count only goes up when a meeting starts, so the busiest moment is always some meeting's start. Checking every start works:

def min_rooms_brute(meetings):
    rooms = 0
    for start, _ in meetings:                   # the busiest moment is always some meeting's start
        in_progress = sum(1 for s, e in meetings if s <= start < e)
        rooms = max(rooms, in_progress)
    return rooms

But it's O(n²). For 10,000 meetings it took 5.3 seconds on our judge, past the 5-second limit, to find 76 rooms. The sweep below found the same 76 in 15.9 milliseconds.

Six meetings on a timeline from 0 to 13, packed into three rooms: room 1 holds [1, 4], [6, 8] and [8, 10]; room 2 holds [2, 5] and [9, 12]; room 3 holds [3, 7]. Below, a step line counts the meetings in progress, rising at each start and falling at each end. Its peak, 3 at once from 3 to 4, is shaded, and the three meetings in progress then are outlined.

The sweep: +1 at a start, −1 at an end

The count changes only at starts and ends. So turn each meeting into two events, +1 at its start and −1 at its end, sort all 2n of them by time, and walk them with a running total. The highest total is the answer.

One detail decides back-to-back meetings. If one meeting ends at 5 and another starts at 5, the room is free at 5, so the end has to come first: −1, then +1. Sorting (time, change) pairs does that for free, because −1 sorts before +1.

Sweep the Events — Meetings sorted by start. The amber line is the event being counted; amber meetings are in progress, the indigo one just started or ended, and dashed ones are over.

int minRooms(const vector<vector<int>>& meetings) {
    vector<pair<int, int>> events;                   // (time, +1 at a start or -1 at an end)
    for (const auto& m : meetings) {
        events.push_back({m[0], 1});
        events.push_back({m[1], -1});
    }
    sort(events.begin(), events.end());              // at a tie -1 sorts first: a room is handed over
    int rooms = 0, inUse = 0;
    for (const auto& [time, change] : events) {
        inUse += change;
        rooms = max(rooms, inUse);
    }
    return rooms;
}

def min_rooms(meetings):
    events = [(s, 1) for s, _ in meetings] + [(e, -1) for _, e in meetings]
    events.sort()                               # by time; at a tie -1 sorts first, so a room is handed over
    rooms = in_use = 0
    for _, change in events:
        in_use += change
        rooms = max(rooms, in_use)
    return rooms

static int minRooms(int[][] meetings) {
    int[][] events = new int[2 * meetings.length][];
    for (int k = 0; k < meetings.length; k++) {
        events[2 * k] = new int[]{meetings[k][0], 1};          // a start
        events[2 * k + 1] = new int[]{meetings[k][1], -1};     // an end
    }
    Arrays.sort(events, (a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0])
                                               : Integer.compare(a[1], b[1]));   // at a tie, ends first
    int rooms = 0, inUse = 0;
    for (int[] e : events) {
        inUse += e[1];
        rooms = Math.max(rooms, inUse);
    }
    return rooms;
}

function minRooms(meetings) {
    const events = [];
    for (const [s, e] of meetings) events.push([s, 1], [e, -1]);   // +1 at a start, -1 at an end
    events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);           // at a tie, ends first
    let rooms = 0, inUse = 0;
    for (const [, change] of events) {
        inUse += change;
        rooms = Math.max(rooms, inUse);
    }
    return rooms;
}

Each prints 3, 1, 1, 2, 1, 2 and 3, the same as counting at every start. [[1, 5], [5, 10]] needs 1 room: the first meeting hands it over at 5. Sorting is O(n log n), the walk is O(n).

Now find the busiest moment yourself. Drag the line, mark the moment you think has the most meetings, and flip the switch to see what changes when a meeting can't hand its room over.

Sweep the Line: move the line, mark the busiest moment, and flip how back-to-back meetings count

When the end still counts: platforms

Minimum Railway Platforms asks the same question about trains, with one difference: a train arriving at 10:30 can't use the platform of a train leaving at 10:30, because that train is still there. The ends count, like closed intervals, so at a tie the arrival goes first:

def min_platforms(arrivals, departures):
    events = [(t, 0) for t in arrivals] + [(t, 1) for t in departures]
    events.sort()                               # at a tie the arrival (0) sorts first: the train leaving still holds its platform
    platforms = in_use = 0
    for _, kind in events:
        in_use += 1 if kind == 0 else -1
        platforms = max(platforms, in_use)
    return platforms

With arrivals [1000, 1010, 1030, 1100] and departures [1030, 1100, 1045, 1130] it returned 3. At 1030 one train leaves and another arrives, and for that moment both need a platform. Sorted with the departure first, the same trains would seem to need 2.

So the tie order is the touching question from Introduction to Intervals once more: does the end belong to the interval? Meetings: no, the room is free. Trains: yes, the platform is still taken.

Which room frees first: a heap

Sometimes you need to know which room, not just how many. Sort the meetings by start and keep a min-heap of the times the rooms in use free up. For each meeting, if the room that frees first is free by its start, reuse it; otherwise open a new room:

import heapq

def min_rooms_heap(meetings):
    frees_at = []                               # a min-heap: when each room in use frees up
    for start, end in sorted(meetings):
        if frees_at and frees_at[0] <= start:   # the room that frees first is free by now: reuse it
            heapq.heapreplace(frees_at, end)
        else:
            heapq.heappush(frees_at, end)       # every room is busy: open another
    return len(frees_at)                        # rooms only ever open, so this is the most at once

It returned 3 for the day above. A room is only ever reused or added, never closed, so the heap's size at the end is the most rooms open at once.

Meeting Rooms III builds on this. Rooms are numbered, a meeting takes the free room with the lowest number, and when every room is busy it waits for the room that frees first and keeps its length. Two heaps: free room numbers, and (time it frees, room) for busy ones.

import heapq

def most_booked(n, meetings):
    free = list(range(n))                       # free room numbers, lowest first
    busy = []                                   # (time it frees, room number)
    count = [0] * n
    for start, end in sorted(meetings):
        while busy and busy[0][0] <= start:     # rooms that have freed by now
            heapq.heappush(free, heapq.heappop(busy)[1])
        if free:
            room = heapq.heappop(free)
            heapq.heappush(busy, (end, room))
        else:                                   # wait for the room that frees first; the meeting keeps its length
            frees, room = heapq.heappop(busy)
            heapq.heappush(busy, (frees + end - start, room))
        count[room] += 1
    return count.index(max(count))

With 2 rooms and meetings [[0, 5], [1, 3], [2, 7], [6, 9], [8, 10]] it returned room 1, the one that held the most meetings, checked against a minute-by-minute simulation.

Sweeping queries too

Minimum Interval to Include Each Query asks, for each query point, the size of the smallest interval that contains it. Sweep the queries in order. Before each one, push the intervals that have started into a min-heap by size; throw out the ones that ended before the query; the top is the answer. Sorting both lists means every interval enters and leaves the heap once:

import heapq

def min_interval(intervals, queries):
    intervals = sorted(intervals)
    heap, i, answer = [], 0, {}                 # heap: (size, end) of the intervals that have started
    for q in sorted(set(queries)):
        while i < len(intervals) and intervals[i][0] <= q:
            s, e = intervals[i]
            heapq.heappush(heap, (e - s + 1, e))
            i += 1
        while heap and heap[0][1] < q:          # it ended before q
            heapq.heappop(heap)
        answer[q] = heap[0][0] if heap else -1
    return [answer[q] for q in queries]

For intervals [[1, 6], [2, 3], [5, 8], [9, 10]] and queries [2, 5, 7, 11] it returned [2, 4, 4, -1]. Query 11 lies outside every interval, so it gets −1. That's O((n + q) log n) for n intervals and q queries, against O(n · q) for checking every interval for every query.

Ties in your language

Meetings need the end first when two events share a time. What each language does at that tie:

Language	Equal times	What to write
C++	`pair<int, int>` compares the change next, so −1 (an end) comes first	nothing extra: `sort(events.begin(), events.end())`
Python	tuples compare the change next: `(5, -1)` before `(5, 1)`	nothing extra: `events.sort()`
Java	only what the comparator compares: the time alone left `{5, 1}` before `{5, -1}`	compare the change too, as the code above does
JavaScript	`a[0] - b[0]` alone leaves them in the order they came	`(a, b) => a[0] - b[0] \|\| a[1] - b[1]`

Java's start first is one room too many: a room handed over at 5 counts twice. For trains the tie goes the other way, so use a key that puts arrivals first.

Spotting it

Clues:

the fewest rooms, platforms, machines or servers so that everything runs;
the most at once: peak load, maximum overlap, the busiest moment;
how many intervals hold each point, or which one does, answered for many points.

And the near-misses:

keep the most in one room: that's choosing, not counting (Interval Scheduling: Sort by End Time).
combine the overlaps: merging (Introduction to Intervals).
loads with amounts on a short route, like passengers per stop: a difference array over the stops (Car Pooling, in Prefix Sum).

Common mistakes

Starts before ends at a tie. For meetings, that counts a handed-over room twice: [[1, 5], [5, 10]] gave 2; the answer is 1.

Returning the heap's size after popping every finished meeting. while frees_at and frees_at[0] <= start:

That's the rooms still busy at the last start, not the most at once: [[1, 10], [2, 3], [4, 5], [11, 12]] gave 1; the answer is 2.

Counting trains like meetings. Departures first at a tie frees a platform that's still taken: the trains above gave 2; the answer is 3.

A delayed meeting that keeps its end. In Meeting Rooms III a waiting meeting starts late and runs just as long. Keeping its old end, [[0, 2], [1, 4], [2, 5], [3, 4], [4, 5]] with 2 rooms returned room 1; the answer is room 0.

Check yourself

Quiz

1 / 6

Multiple choice

How many rooms does [[1, 4], [2, 5], [3, 7], [6, 8], [8, 10], [9, 12]] need?

Practice problems

From easier to harder:

Meeting Rooms II: the sweep, or a heap of end times.
Minimum Railway Platforms: the same count, with arrivals first at a tie.
Minimum Interval to Include Each Query: sorted queries, a heap by size.
Meeting Rooms III: two heaps, free rooms and busy ones, with delays.

That's the Intervals section. The Intervals Quiz checks all three lessons.