How does a sweep line find the maximum number of sessions open at once in a login/logout log?
answer
- the interval interiors tell you nothing
- the count changes only at boundaries
- two events per session, not one
- sort the boundary events by coordinate
- running sum, and remember its maximum
basics
~20 sA sweep line throws away the intervals and keeps only their boundaries: +1 at each login coordinate, -1 at each logout. Sort those events by coordinate, scan once with a running sum, and remember the largest sum seen.
solid answer
~40 sThe number of concurrently open sessions changes only at a boundary, so the interval bodies carry no information. Flatten each session `[login, logout)` into two events, `(login, +1)` and `(logout, -1)`, giving `2n` events for `n` sessions. Sort them by coordinate, then scan left to right maintaining a running sum: after processing every event at or before coordinate `x`, the sum is exactly how many sessions cover `x`. The answer is the maximum that running sum ever reaches, and the coordinate where it happened is free bookkeeping. Cost is `O(n log n)` time, dominated entirely by the sort — the scan itself is one linear pass — and `O(n)` extra space for the event list. If sessions carry weights (seats, bytes, licences), use `+w` and `-w` instead of `+1` and `-1`; nothing else changes.
go deeper
Be ready to state the recipe cleanly: two events per interval, sort by coordinate, running sum, track the maximum. Say out loud that the maximum is tracked during the scan, not read off at the end.
Explain why the count can only change at a boundary, and derive the O(n log n) bound by pointing at the sort rather than the scan. Mention that weighted deltas generalise the same pass.
Show that the single pass also yields the peak's location, the occupancy profile and a capacity feasibility check, and say what you would validate about the event stream before trusting the number.
Own the framing: this is a step-function maximum, so the representation choice — sort-then-scan versus counting into a bounded coordinate domain — is the real decision once the data outgrows one machine.
## The question behind the question "How many things are happening at the same time, at the busiest moment?" is one of the most common shapes in real work: peak concurrent sessions on a service, peak simultaneous calls on a switchboard, peak parallel jobs on a fleet. The input is a pile of `[start, end)` ranges; the output is a single number (and usually the coordinate where it occurred). The naive instinct is to compare sessions against each other, or to walk time forward one tick at a time and count who is active. Both are avoidable. The sweep line is the standard answer, and it rests on one observation. ## The observation: the count is piecewise constant Define `f(x)` = the number of sessions covering coordinate `x`. Between two consecutive boundary coordinates, no session starts and none ends, so `f` cannot change. `f` is a step function whose only steps are at session endpoints. Therefore the maximum of `f` is attained at (or immediately after) some boundary, and you never have to look anywhere else. The interiors of the intervals are dead weight. ## The mechanism 1. **Flatten.** Each session `[s, e)` becomes two events: `(s, +1)` and `(e, -1)`. For `n` sessions you get `2n` events. The session identity is usually irrelevant from here on — that is the point of the technique, and why it is so cheap. 2. **Sort** the events by coordinate ascending. (When two events share a coordinate, the order between them matters and is decided by whether your intervals are half-open or closed — a separate, load-bearing detail.) 3. **Scan** once, left to right, maintaining `current = current + delta` and `best = max(best, current)`. Why the running sum is the coverage count: at any point in the scan, `current` is the number of `+1` events already applied minus the number of `-1` events already applied — that is, sessions that have started and have not yet ended. That is the definition of "open right now". The sum telescopes correctly for any nesting or overlap pattern, including sessions fully contained inside others. ## Cost - Time `O(n log n)`: building `2n` events is linear, the scan is linear, the comparison sort dominates. - Space `O(n)` for the event list. You can sort start coordinates and end coordinates as two separate sorted sequences and merge-walk them, which avoids materialising event pairs but does not change the asymptotics. - The sort is the only super-linear part, so any way to skip it drops you to `O(n)`. If events already arrive ordered by coordinate — which a real event log often does — the scan alone answers the question in one streaming pass. If coordinates are small bounded integers, you can count into buckets indexed by coordinate and scan the buckets, trading memory proportional to the coordinate domain for the sort. ## What the sweep gives you beyond the maximum Because the scan reconstructs the whole step function, the same pass answers a family of questions for free: the coordinate at which the peak begins, the full occupancy profile, how long the system spent above some threshold, or a feasibility check against a capacity limit (stop the moment `current` exceeds it). The peak is not a point but a stretch: the count stays at its maximum from the event that raised it until the next event, and reporting a single timestamp for the peak without saying it holds until the next boundary is a common sloppiness. ## Why pairwise comparison is the wrong tool Counting overlapping *pairs* is `O(n^2)` and, more importantly, answers a different question. Three sessions can pairwise overlap in three pairs while all three are open together — or, with different shapes, produce the same pair count with only two ever open at once. Maximum concurrency is a property of the deepest point, not of the pair count, and the sweep computes it directly. ## The failure modes to name in an interview - **Sorting only the starts.** Sorting sessions by start and counting how many you have seen gives the total number of sessions started, not how many are open. - **Reading the final running sum as the answer.** When every session ends inside the window the final sum is zero; the answer is the running *maximum*, tracked during the scan. - **Simulating every tick.** Stepping one unit at a time is `O(range)`, which is catastrophic for high-resolution timestamps and unnecessary given the step-function argument. - **Forgetting the tie rule.** Two events on the same coordinate must be ordered deliberately, or the peak is off by one whenever boundaries coincide.
- Why is this O(n log n) and not O(n)?The flattening and the scan are both linear; the comparison sort of the `2n` events is the only super-linear step, so it sets the bound. Remove the sort — events already arriving in coordinate order, or coordinates small enough to count into buckets — and the whole thing becomes a single linear pass.
- Does the peak concurrency occur at an instant or over a stretch?Over a stretch. The count is constant between consecutive event coordinates, so once an event pushes the running sum to its maximum, that value holds until the next event coordinate. Report the peak as the half-open span between those two boundaries, not as a single point.
- How would you extend the same sweep to answer 'how long were more than 100 sessions open?'Keep the previous event coordinate during the scan. Before applying each event, if the current count exceeds 100, add `coordinate - previous` to an accumulator. One extra variable, same single pass, same asymptotics — the sweep reconstructs the whole occupancy profile, not just its maximum.
It is a turnstile count for a room: you never track who is inside, only the clicks in and out, and the busiest moment is the highest the counter ever climbed.
saying these in an interview costs you the question
- Sorts sessions by start and counts how many were seen
- Reports the running sum after the last event as the peak
- Counts overlapping pairs and calls that concurrency
- Walks the timeline one tick at a time
- Keeps whole intervals in the scan instead of boundary events