---
title: "Sweep line (event counting)"
url: https://algopath.pro/patterns/sweep-line
language: en
summary: "Turn each interval into a start event and an end event. Then sort all the events by position and walk them with a counter."
updated: 2026-08-24
---

# Sweep line (event counting)

Turn each interval into a start event and an end event. Then sort all the events by position and walk them with a counter.

## 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.

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

## When should you use Sweep line (event counting)?

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

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

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

## 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.

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

## 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.

## JavaScript

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

## Python

```python
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
```

## PHP

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