cf.completefrontend
GREEDY & INTERVALS · CORE

Sweep line

Turn ranges into start and end events, sort the events by time, and walk through them in order while keeping a running count.

Time O(n log n)Space O(n)8 practice problemsStep-through picture

The idea

Some range questions ask what happens at each moment: the most meetings happening at once, the busiest second on a server, whether a shuttle is ever over capacity. Checking every moment one by one is slow when times are large.

A sweep line imagines a vertical line moving across a timeline from left to right. It only stops where something changes: where a range starts or ends. So each range [start, end] becomes two events: +1 at start and -1 at end. Sort all events by time and walk through them, adding each change to a running count, active.

At any point in the walk, active is how many ranges cover that moment. The highest value it reaches is the most ranges that overlap at once. Ties need care: at the same time, the order of +1 and -1 events decides whether touching ranges count as overlapping.

An everyday example

Counting people in a room from the door log

A meeting room has a door log: each person's arrival and departure time. To find the most people in the room at once, you don't check every minute of the day. You put all arrivals and departures on one list in time order and read it top to bottom, adding one for each arrival and taking one away for each departure. The highest count you see is the answer.

How the example maps to the code
In the exampleIn the code
An arrival in the logevents.push([start, 1])
A departure in the logevents.push([end, -1])
Reading the log in time orderevents.sort(...)
People in the room right nowactive
The most people at oncebest

From the slow way to sweep line

  1. The obvious way to find the most ranges running at once is to check every moment. For each time t from the earliest start to the latest end, count the ranges that cover t. With n ranges and a time span of T units, that is O(n · T) work, and T might be a billion milliseconds.
  2. Most of those moments are boring. Between two times where some range starts or ends, the set of ranges covering the moment doesn't change, so neither does the count. Only the 2n start and end times can change the answer.
  3. So turn each range into two events: at start the count goes up by one, and at end it goes down by one. Visit the events in time order and add each change to a running total, active. Then active is the count right after each event, and no range is ever checked twice.
  4. One question is left: what happens at equal times? If one range ends at 4 and another starts at 4, they shouldn't count as overlapping for meetings, so the -1 must come before the +1. Sort by time, then by change, walk the events once, and keep the largest active in best. That loop is a sweep line.

How it works

  1. For each interval [start, end], create two events: [start, 1] and [end, -1].
  2. Sort the events by time. For equal times, put -1 before +1, so a range that ends exactly when another starts doesn't count as overlapping.
  3. Set active = 0 and best = 0.
  4. Walk through the events in order and add each change to active.
  5. After each event, set best to the larger of best and active.
  6. Return best, the most intervals that overlap at once.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function maxOverlap(intervals) {
  2. const events = [];
  3. for (const [start, end] of intervals) {
  4. events.push([start, 1]);
  5. events.push([end, -1]);
  6. }
  7. events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
  8. let active = 0;
  9. let best = 0;
  10. for (const [, change] of events) {
  11. active += change;
  12. best = Math.max(best, active);
  13. }
  14. return best;
  15. }

How fast it is

TimeO(n log n)
Extra memoryO(n)

Sorting the 2n events costs O(n log n). The walk is one pass. The events list holds 2n items.

  • Best caseO(n)

    The ranges don't overlap and arrive in time order, like [[1, 2], [3, 4]]. The events are then already sorted, V8's TimSort finishes in one pass, and the walk is one more.

  • Average caseO(n log n)

    Ranges in any order: sorting the 2n events costs O(n log n), and the walk adds O(n).

  • Worst caseO(n log n)

    The same as average. The walk is always 2n steps, and the sort decides the cost.

Common mistakes

  • Sorting ties the wrong way, so [1, 3] and [3, 5] count as overlapping when they shouldn't (or the other way). Decide which event comes first at equal times.
  • Building an array with one slot per time unit when times go up to 10^9. Sort the events instead.
  • Checking best before applying the change, which reads the count from before the event.
  • Forgetting that events.sort with no compare function sorts arrays as text, so [10, 1] comes before [9, 1].

When to use it

Look for these clues in a problem:

  • The question asks about how many ranges overlap at the same moment: the most at once, or if a limit is ever exceeded.
  • It asks for the busiest time, the number of rooms or servers needed, or capacity over time.
  • Times can be huge (up to 10^9), so an array indexed by time won't fit.
  • You need to process starts and ends in time order, sometimes with more state than a count (like a heap of active heights).

Check yourself

Answer each one in your head first, then open it.

Why is it enough to look at active right after each event?

Between two event times nothing starts or ends, so the count is the same at every moment of that gap. Each gap's count is the value of active right after the event that opens it.

Why isn't a[0] - b[0] alone a safe compare function for the events?

Events with the same time then stay in the order they were pushed, which depends on the input order. [[4, 6], [1, 4]] would return 2 while [[1, 4], [4, 6]] returns 1.

How many events are sorted for 1,000 ranges, and about how many comparisons does that take?

2,000 events, one +1 and one -1 per range. Sorting them takes on the order of 2000 × log₂ 2000, roughly 22,000 comparisons.

What must active be after the last event, and why?

0. Every range adds exactly one +1 and one -1, so all the changes add up to zero.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 8 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The rule the loop keeps: after the events up to some point have been handled, active equals the number of ranges that have started but not yet ended. It starts at 0 before any event. Each +1 is a range starting and each -1 is a range ending, so adding change keeps the count exact.

Between two neighboring event times nothing starts or ends, so every moment in that gap is covered by exactly active ranges, the value right after the earlier event. Every moment of the timeline falls in some gap, so the highest count anywhere is one of the values active takes. Taking the max after each event finds it.

The tie order makes the count match the problem's meaning. Sorting -1 before +1 at equal times means a range that ends at 4 is gone before a range that starts at 4 arrives, which is right for meetings, where the end time isn't included. The loop runs exactly 2n times and then stops, with active back at 0.

Going deeper

3 more ideas

Why the count only changes at events

Between two neighboring event times, no range starts or ends, so the set of ranges covering every moment in that gap is the same. That's why checking the count right after each event is enough: the biggest count over the whole timeline is reached at some event.

Why it takes O(n log n) time

There are 2n events. Sorting them costs O(n log n), and the walk is O(n). Memory is O(n) for the events. If times are small whole numbers, a difference array (add at start, subtract at end, then a running sum) does the same in O(n + maxTime).

Sweeps that keep more than a count

The same walk can keep richer state. To draw the outline of overlapping rectangles, keep the heights of the rectangles currently covering the sweep line in a heap, and record a point whenever the tallest height changes. To assign each meeting a room, keep a heap of rooms by when they become free.

Work it by hand

Every step in a table, with why

Find the most ranges running at once. At times 4 and 9, one range ends exactly when another starts.

intervals = [[3, 7], [1, 4], [4, 6], [5, 9], [9, 10]]

StepEvent [time, change]activebestWhat happensWhy
1-00sort the 10 eventsSorted by time, with -1 before +1 at equal times: [1, 1], [3, 1], [4, -1], [4, 1], [5, 1], [6, -1], [7, -1], [9, -1], [9, 1], [10, -1].
2[1, 1]11[1, 4] startsThe first range begins.
3[3, 1]22[3, 7] startsTwo ranges now run together.
4[4, -1]12[1, 4] ends firstAt time 4 the end is handled before the start, so [1, 4] and [4, 6] are never counted together.
5[4, 1]22[4, 6] startsThe count is back to 2, not 3.
6[5, 1]33[5, 9] starts: new bestFrom time 5 to 6, three ranges run: [3, 7], [4, 6], and [5, 9].
7[6, -1]23[4, 6] endsThe count drops, and best keeps the 3.
8[7, -1]13[3, 7] endsOnly [5, 9] is left running.
9[9, -1]03[5, 9] endsAnother tie at time 9: the count drops to 0 before [9, 10] starts.
10[9, 1]13[9, 10] startsThe last range begins.
11[10, -1]03[9, 10] endsThis is the last event. active is back to 0, as it must be once every range has ended.

It returns 3. If +1 came first at equal times, time 4 would briefly count 3 too. The answer here would still be 3, but [[1, 4], [4, 6]] alone would give 2 instead of 1.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Sweep lineO(n log n)O(n)Times are large or not whole numbers, and you need the most overlap or a capacity check.
Difference arrayO(n + T)O(T)Times are small whole numbers, like minutes in a day, and you may also want the count at every moment.
Min-heap of end timesO(n log n)O(n)You need to know which room or lane each range goes into, not just how many rooms.
Check every momentO(n · T)O(1)Only when the time span T is tiny and the simplest code matters most.

Extra memory: O(n) for the 2n events. The walk itself uses two numbers, active and best.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Sweep line and the other approaches, on a scale where each line up is 10 times more steps.
  • Sweep line, Min-heap of end times O(n log n)
  • Difference array O(n + T)
  • Check every moment O(n · T)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Sweep line339,96620 million
Difference array202,0002 million
Min-heap of end times339,96620 million
Check every moment1001 million1 trillion

Inputs that need care

5 tricky inputs
No ranges: []
There are no events, the loop never runs, and it returns 0.
Touching ranges: [[1, 4], [4, 6]]
The -1 at time 4 sorts first, so active goes 1, 0, 1, 0 and it returns 1. If touching should count as overlapping, put +1 first with a[0] - b[0] || b[1] - a[1], and it returns 2.
A zero-length range: [[5, 5]]
Its -1 sorts before its +1, so active goes to -1 and back to 0, and best stays 0. If an instant should count as one running range, sort +1 first or handle such ranges apart.
Identical ranges: [[2, 8], [2, 8], [2, 8]]
The three +1 events at time 2 come first, so active reaches 3 and it returns 3.
Huge times: [[0, 1e12]]
Only the two event times are stored, so the size of the numbers doesn't matter. An array with one slot per time unit would need a trillion slots.

Variations and follow-ups

Twists interviewers add

Difference array

When times are small whole numbers, skip the sort. Make an array diff with one slot per time unit, add 1 at start, subtract 1 at end, and take a running sum. That is O(n + T) time and O(T) memory for a time span of T.

Capacity check

If each trip carries some passengers, push [start, passengers] and [end, -passengers] instead of 1 and -1. Sweep the same way, and the answer is no as soon as active goes over the capacity.

Assigning rooms with a heap

To say which room each meeting uses, sort meetings by start and keep a min-heap of the times rooms become free. Before each meeting, reuse a room whose meeting has ended. The heap never grows past the sweep's best.

Sweeping in two dimensions

For rectangles, move a vertical line across the x values and keep the y ranges of the rectangles it crosses in a tree, like a segment tree. That finds the area covered by all rectangles, or the outline of a row of buildings, in O(n log n).

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "the most at the same time", "the fewest rooms", "is the capacity ever exceeded", or "the busiest moment". All of them are a running count over sorted events.
  • Explain the events out loud: "each range becomes +1 at its start and -1 at its end, I sort them and keep a running total". Then say how you break ties and why.
  • Test by hand: touching ranges, identical ranges, and an empty list. Check that active is 0 after the last event; if it isn't, the events are wrong.
  • A common follow-up is "now say which room each meeting goes in". Switch to sorting by start with a min-heap of end times, and note that the heap never holds more than the sweep's answer.

Where frontend code uses it

The same idea in real UI code
  • A calendar day view finds how many events overlap at each moment to decide how many columns to split overlapping event cards into.
  • Performance tools find the moment with the most network requests in flight by sweeping over each request's start and end time.
  • Video editing timelines count how many clips are stacked at each time to decide how many tracks to show.

Related algorithms