Sweep line (event counting)

How does Sweep line (event counting) work?

Each interval becomes two events. One start at the left coordinate, one end at the right.

Put every event into a single list. A start carries plus one, an end carries minus one.

Sort that list by coordinate. Ties need a rule, and the rule depends on the question.

Walk the sorted events and keep a running counter. It always holds how many intervals are open.

Record whatever the question asks at each step. Usually that is the highest the counter reached.

The coordinates never have to be dense. Only their relative order matters.

1. meetings [1, 4], [2, 5], [7, 9]Three meetings become six separate events.
2. 1+, 2+, 4-, 5-, 7+, 9-The events are sorted by time. The intervals no longer exist.
3. count = 1 at time 1The first meeting opens. One room is in use.
4. count = 2 at time 2The second opens before the first ends. Two rooms are needed.
5. count = 0 at time 5Both close before 7 arrives. The peak was 2.

function maxOverlap(intervals) {
    const events = [];
    for (const [start, end] of intervals) {
        events.push([start, 1]);
        events.push([end, -1]);
    }
    events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
    let active = 0;
    let best = 0;
    for (const [, delta] of events) {
        active += delta;
        best = Math.max(best, active);
    }
    return best;
}

A worked example of Sweep line (event counting)

How many meeting rooms are needed

You get the start and end time of every meeting. Find the smallest number of rooms that holds them all.

Two meetings need separate rooms when they overlap.

Sort the start times and the end times into two lists.

Walk them together: a start takes a room, an end gives one back. The peak count is the answer.

function minMeetingRooms(intervals) {
    const starts = intervals.map((i) => i[0]).sort((a, b) => a - b);
    const ends = intervals.map((i) => i[1]).sort((a, b) => a - b);

    let rooms = 0;
    let best = 0;
    let e = 0;

    for (const start of starts) {
        // every meeting already finished hands its room back first
        while (ends[e] <= start) {
            rooms--;
            e++;
        }

        rooms++;
        best = Math.max(best, rooms);
    }

    return best;
}

When should you use Sweep line (event counting)?

These phrases in a problem statement point here:

• •maximum number of overlapping meetings/intervals at once
• •minimum rooms/resources needed
• •busiest moment in time
• •how many intervals cover a given point
• •events happening at the same time

What is Sweep line (event counting) confused with?

• Intervals: merge & insert: Merging keeps intervals whole and joins the ones that touch. A sweep forgets them and counts.
• Difference array: That is a sweep whose coordinates are array indices. It needs a small, dense range.
• Binary heap / priority queue: A heap holds the open intervals so you know which ends soonest. The counter only knows how many.
• Prefix sums: Prefix sums answer over fixed positions in an array. A sweep walks events in sorted order.

Common mistakes with Sweep line (event counting)

• No rule for events at the same coordinate

  Does an end at time 5 free a room for a start at 5? Decide that, then encode it.

• Sorting the intervals instead of the events

  A sweep needs starts and ends interleaved. Sorting whole intervals keeps each pair glued together.

• Reading the counter after the walk

  The answer is normally the peak, not the final value. The final value is usually zero.

• Indexing an array by the coordinate

  Timestamps up to 1e9 cannot be array indices. Sort the events instead of allocating.

Which interview problems use Sweep line (event counting)?

• Meeting rooms II: The peak counter is the number of rooms.
• Car pooling: Passengers get on and off along one route.
• My calendar III: The counter must never pass the booking limit.
• Number of flowers in full bloom: Count how many ranges cover each query day.
• The skyline problem: A sweep with a heap holding the live heights.
• Employee free time: Every gap where the counter sits at zero.
• Maximum population year: Births and deaths as events along a timeline.

What is the time and space complexity of Sweep line (event counting)?

O(n log n)

n intervals give 2n events, so O(n log n) for the sort. The walk itself is O(n).