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.

Sources: Wikipedia: Sweep line algorithm

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;
}

function maxOverlap(intervals: number[][]): number {
    const events: number[][] = [];
    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;
}

def max_overlap(intervals):
    events = []
    for start, end in intervals:
        events.append((start, 1))
        events.append((end, -1))
    events.sort()
    active = 0
    best = 0
    for _, delta in events:
        active += delta
        best = max(best, active)
    return best

function maxOverlap(array $intervals): int {
    $events = [];
    foreach ($intervals as [$start, $end]) {
        $events[] = [$start, 1];
        $events[] = [$end, -1];
    }
    usort($events, fn($a, $b) => $a[0] <=> $b[0] ?: $a[1] <=> $b[1]);
    $active = 0;
    $best = 0;
    foreach ($events as [, $delta]) {
        $active += $delta;
        $best = max($best, $active);
    }
    return $best;
}

    public static int maxOverlap(int[][] intervals) {
        List<int[]> events = new ArrayList<>();
        for (int[] interval : intervals) {
            events.add(new int[] { interval[0], 1 });
            events.add(new int[] { interval[1], -1 });
        }
        events.sort(Comparator
            .comparingInt((int[] e) -> e[0])
            .thenComparingInt(e -> e[1]));
        int active = 0;
        int best = 0;
        for (int[] event : events) {
            active += event[1];
            best = Math.max(best, active);
        }
        return best;
    }

    public static int MaxOverlap(int[][] intervals) {
        var events = new List<int[]>();
        foreach (var interval in intervals) {
            events.Add(new int[] { interval[0], 1 });
            events.Add(new int[] { interval[1], -1 });
        }
        events.Sort((a, b) => a[0] != b[0]
            ? a[0].CompareTo(b[0])
            : a[1].CompareTo(b[1]));
        int active = 0;
        int best = 0;
        foreach (var e in events) {
            active += e[1];
            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)?

Use Sweep line (event counting) when the problem statement says “maximum number of overlapping meetings/intervals at once”, “minimum rooms/resources needed” or “busiest moment in time”. A solution built on it usually runs in O(n log n).

• •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

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is Sweep line (event counting) confused with?

Sweep line (event counting) is most often confused with Intervals: merge & insert, Difference array, Binary heap / priority queue and Prefix sums.

• 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 always zero, because every start has a matching end.

• 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)?

Interview problems solved with Sweep line (event counting) include Meeting rooms II, Car pooling, My calendar III, Number of flowers in full bloom, The skyline problem, Employee free time and Maximum population year.

• 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)?

The target complexity of Sweep line (event counting) is O(n log n).

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