Sweep line algorithm: intervals become events, then one sorted pass
Elman Huseynov · 2026-11-22
Short answer. The sweep line algorithm turns intervals into events. An interval start is plus one, an end is minus one. Sort the events by coordinate. Walk left to right with a counter. At any moment the counter equals the coverage at that point. Time O(n log n). Below: trigger words, Python code, a traced run and the tie-breaking rule.
What is a sweep line?
Picture a vertical line moving along the axis from left to right. It passes interval starts and ends. At each point you know how many intervals sit under the line.
There are many intervals, but only 2n interesting points. The starts and the ends. Between them nothing changes. So you only look at the events.
The name comes from computational geometry. The same idea works on a plain number line.
maxOverlap([[1, 4], [2, 5], [7, 9], [3, 6], [5, 8]])| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|
| [1,4] | ■ | ■ | ■ | ■ | |||||
| [2,5] | ■ | ■ | ■ | ■ | |||||
| [7,9] | ■ | ■ | ■ | ||||||
| [3,6] | ■ | ■ | ■ | ■ | |||||
| [5,8] | ■ | ■ | ■ | ■ |
How many intervals are open at the busiest moment? Each interval is a row on the timeline.
The pattern page: when to use it, and a template in six languages
How does the sweep line work step by step?
- For each interval create two events: the start with +1, the end with -1.
- Sort the events by coordinate. On a tie, -1 first if ends are open.
- Walk the events and add each delta to a counter.
- After each event the counter is the coverage at that point. Record the maximum or the point you need.
The tie order is the only subtle part. One meeting ends at 10, another starts at 10. They do not overlap. So minus goes first.
What does one run look like?
Meetings [0, 30], [5, 10], [15, 20]. Events in order: 0 plus, 5 plus, 10 minus, 15 plus, 20 minus, 30 minus. Counter after each: 1, 2, 1, 2, 1, 0. Maximum 2, two rooms needed.
Add a meeting [10, 12]. Events (10, -1) and (10, +1) sit together. Minus first: counter 1, then 2. The answer stays 2. Plus first would give 3, which is wrong.
How do you write a sweep line in Python?
def min_meeting_rooms(intervals):
events = []
for s, e in intervals:
events.append((s, 1))
events.append((e, -1))
events.sort() # on a tie, -1 sorts before +1
rooms = best = 0
for _, delta in events:
rooms += delta
best = max(best, rooms)
return best
def max_overlap_point(intervals):
events = sorted([(s, 1) for s, e in intervals] + [(e, -1) for s, e in intervals])
count = best = 0
point = None
for x, delta in events:
count += delta
if count > best:
best, point = count, x
return point, best
def car_pooling(trips, capacity):
delta = {}
for people, start, end in trips:
delta[start] = delta.get(start, 0) + people
delta[end] = delta.get(end, 0) - people
load = 0
for x in sorted(delta):
load += delta[x]
if load > capacity:
return False
return True
Tuples (coordinate, delta) sort themselves correctly. On an equal coordinate, -1 is smaller than +1. That gives the right order for free.
How does the sweep line compare with its neighbours?
| Pattern | Question | Time | Use when |
|---|---|---|---|
| Sweep line | How many intervals at a point, where is the peak | O(n log n) | Any coordinates, including huge ones |
| Difference array | The same | O(n + max) | Small integer coordinates |
| Merge intervals | Join overlapping ones | O(n log n) | You need the intervals, not a count |
| Heap of ends | Number of rooms | O(n log n) | You need to know which room freed up |
How does the sweep line solve Meeting Rooms II?
The minimum number of rooms equals the peak number of concurrent meetings. That is the first function above. A heap of end times gives the same answer. Events are shorter and clearer.
How does it solve The Skyline Problem?
Buildings are intervals with a height. Sweep along x. At a building start, add its height to a structure. At its end, remove it. After each event look at the current maximum height. If it changed, record a point.
The structure is a heap with lazy deletion. The tie order here is special: tall starts first, low ends last.
When does a problem need a sweep line?
- "How many intervals cover a point", "maximum concurrent".
- "Does the capacity hold" with pickups and drop-offs.
- "Minimum number of rooms, platforms, servers."
- "Skyline", "union of rectangles".
What mistakes break the solution?
- Plus before minus on a tie. Touching intervals count as overlapping.
- Forgetting that closed ends need the opposite order.
- Taking the maximum before applying the event, not after.
- Using a difference array on coordinates up to a billion. The array is huge.
How do you explain the sweep line in an interview?
Say: I turn intervals into plus one and minus one events. I sort them and walk with a counter. Give O(n log n) from the sort. Name the tie order separately.
Then compare with the difference array and say when to use each. It shows you see two patterns, not one.
Drill this pattern on the sweep line page. The neighbouring pattern lives on the difference array page.
FAQ
How is a sweep line different from a difference array?
Same idea: deltas at coordinates. A difference array stores them in an array and needs small coordinates. A sweep line stores them in a sorted list and handles any.
How do you find the point of maximum coverage?
The second function above. Record the coordinate where the counter first reached its maximum.
Does it work in two dimensions?
Yes, for the area of a union of rectangles. Sweep along x. Keep a segment tree or sorted list along y. That one is a hard problem.
Where does the sweep line show up in real systems?
Capacity planning: how many servers are busy at each moment. Calendars counting conflicts. Graphics rendering overlaps.