Sweep Line Algorithm

Question 1

In Meeting Rooms II, what do sweep line events represent?

Accepted Answer

Meeting start and end times along the timeline — Each meeting creates two events: +1 at start time (need a room) and -1 at end time (room freed). Max concurrent sum = min rooms needed.

Question 2

The sweep-line (plane-sweep) technique processes geometric/interval data by…

Accepted Answer

Events in a chosen dimension, maintaining a live active set — A conceptual line sweeps across the plane (or number line); events (starts, ends, intersections) are handled in sorted order, maintaining state as the line moves.

Question 3

For the 'minimum number of meeting rooms' problem, sweep-line treats each meeting as…

Accepted Answer

Two events: a start (+1) and an end (−1) — Sorting start/end events and tracking a running count of active meetings; the maximum simultaneous count is the minimum rooms needed — O(n log n).

Question 4

What dominates the time complexity of most sweep-line algorithms?

Accepted Answer

Sorting the events, roughly O(n log n) — Events must be ordered first (O(n log n)); the sweep then processes them in O(n) or O(n log n) using a balanced structure, so sorting usually dominates.

Question 5

To find whether any of n line segments INTERSECT, the Bentley-Ottmann sweep runs in…

Accepted Answer

By tracking a sorted active set as the sweep moves — A vertical sweep maintains segments ordered by y in a balanced BST, checking only neighbors for intersection — far better than the O(n²) all-pairs check.

Question 6

The 'active set' in a sweep-line algorithm holds…

Accepted Answer

The set of shapes currently crossing the sweep line — As the line advances, objects are inserted when they start and removed when they end; the active set represents what's 'currently present' at the line's position.

Question 7

For the SKYLINE problem (building silhouettes), the sweep processes building edges and uses a…

Accepted Answer

Processing start/end x-events, tracking the tallest active building — At each x-event you add/remove a building height; a max-heap gives the current skyline height, and key-points are emitted when it changes — O(n log n).

Question 8

Merging/counting OVERLAPPING INTERVALS is efficiently done by…

Accepted Answer

By sorting endpoints and tracking active overlap count — After sorting by start, a single pass merges intervals whose start ≤ current end, extending the end — O(n log n) dominated by the sort.

Question 9

The area of the UNION of axis-aligned rectangles is computed by a vertical sweep plus…

Accepted Answer

Sweeping x-coordinates, tracking covered y-length — At each x-event you update which y-intervals are covered (often coordinate-compressed in a segment tree) and accumulate width × covered-height — O(n log n).

Question 10

Why sort the events before sweeping?

Accepted Answer

So the sweep processes them in a consistent, correct order — The sweep's correctness relies on processing events in the order the line encounters them; sorting establishes that order.

Meeting rooms

Test your knowledge

In Meeting Rooms II, what do sweep line events represent?

The short version

In more depth

Events in Motion

When to reach for this

Interview Questions

References & Further Reading

Related topics

Love this visualization?