We use necessary cookies to run the site (sign-in and language). If you accept, we also load Google Analytics to see which pages are used, and Google reCAPTCHA to keep spam off the contact and bug-report forms. Privacy policy

← Blog
How to prepare

Sweep line algorithm: intervals become events, then one sorted pass

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

Most intervals open at the same time
maxOverlap([[1, 4], [2, 5], [7, 9], [3, 6], [5, 8]])
timeline (one row per interval)
123456789
[1,4]■■■■
[2,5]■■■■
[7,9]■■■
[3,6]■■■■
[5,8]■■■■
events
empty
active = 0best = 0

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?

PatternQuestionTimeUse when
Sweep lineHow many intervals at a point, where is the peakO(n log n)Any coordinates, including huge ones
Difference arrayThe sameO(n + max)Small integer coordinates
Merge intervalsJoin overlapping onesO(n log n)You need the intervals, not a count
Heap of endsNumber of roomsO(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.