Intervals and sweep
What order makes overlapping ranges easy?
Two notices for one outage
The banks a payments service works with send it their maintenance windows, and a status page tells merchants when UPI will be down. Tonight there are 3,200 windows from 41 banks, and plenty of them overlap.
The first version takes the windows one at a time and checks each against every notice already on the page: merge into the first one it overlaps, or add a new notice. That is up to 5.1 million comparisons, which is fine. The output is wrong. For one group of banks the page shows two notices, 1:00 to 6:00 a.m. and 5:00 to 7:00 a.m., and a merchant writes in to ask which outage is the real one.
Trace it. The windows arrived as 1:00 to 3:00, 5:00 to 7:00 and 2:00 to 6:00. The first made a notice. The second did not touch it, so it made a second notice. The third overlapped the first and stretched it to 1:00 to 6:00. Nothing went back to see that the stretched notice now overlaps the second. Overlaps can form chains, where two windows are joined only through a third, and one pass in arrival order does not see chains.
Repeating the pass until nothing changes works, at millions of comparisons a pass. The windows arrived in an unlucky order, and a single pass in a better one might need no repeats at all.
Pause and predict You want to process the windows in an order where each window needs to be compared with only one thing. Which order, and which thing?
The order that makes one comparison enough
Two intervals overlap when each one starts no later than the other ends: a.start ≤ b.end and b.start ≤ a.end. Checking every pair takes O(n²) time, and for merging, checking pairs is not even enough: [1, 3] and [5, 7] do not overlap, yet [2, 6] overlaps both and joins all three into [1, 7].
Sorting by start solves both problems. Walk the intervals in that order and keep a list of merged blocks. Each new interval either starts at or before the end of the last block, and extends it, or starts after the last block ends, and opens a new block.
When an interval extends the block, the block's new end is the larger of the two ends, so that an interval lying inside the block, such as [2, 3] inside [1, 10], does not shrink it. Sorting costs O(n log n) and the walk costs O(n). A walk like this, over items sorted by position, is called a sweep line.
Three questions, three orders
Pause and predict Now a different question: keep as many intervals as possible so that no two of the kept ones overlap. What should you sort by?
Why the earliest end is safe
Keeping the most intervals that do not overlap means choosing which ones to keep, and a rule for choosing needs a proof that it never does worse than the best answer. The rule here: take the interval that ends first, drop every interval that overlaps it, and repeat on what is left.
The other sort keys fail, and each has a short counterexample. Sorting by start, [1, 10], [2, 3], [4, 5] keeps [1, 10] first, which overlaps both others, so it keeps one interval when two would fit. Taking the shortest first, [1, 5], [4, 7], [6, 10] keeps [4, 7] first, which overlaps both others, so again it keeps one when two would fit.
Minimum Number of Arrows uses the same proof. The balloon that ends first must be hit by some arrow, and the best place for that arrow is at that balloon's end. Every other balloon ends there or later, so any balloon that an arrow further left would hit, an arrow at this end hits too.
Why the depth is the answer
The question "how many rooms are needed?" asks for the depth: the largest number of intervals that share one point. Two facts show that the depth is the answer. If d intervals share a point, they all conflict with each other, so at least d rooms are needed. And d rooms are enough. Go through the intervals sorted by start; when an interval begins, the busy rooms hold intervals that contain its start. Together with the new interval they all share that point, so there are at most d - 1 of them, and one of the d rooms is free.
A min-heap of end times stands for the busy rooms. At each new start, pop every end that comes before it, then push the new end. The heap's size is then the depth at that start. The depth is always largest at some interval's start, so the largest size the heap reaches is the answer.
You can count the same thing without a heap, the way Car Pooling did. Make an event of +1 where each interval starts and -1 just after it ends, sort the events by time, and add them up in order. The running sum is the depth.
How to recognise it
Pause and predict Do [1, 4] and [4, 6] overlap?
Every problem in this unit uses closed intervals, which include both endpoints, and one of them says outright that intervals which only touch do not overlap. Meetings are usually half-open, which means the end time is not included. In an interview, say out loud which one you are assuming.
The ones that only look like it
- Many additions over ranges, read once at the end, on small coordinates: a difference array is enough, and no sort is needed. That is prefix sums.
- The k best values, or taking the smallest again and again, when the items have no start and end: a heap alone is the answer. That is heaps.
- Choices along a line that are not about intervals, such as jumps or gas stations: the proof is the same kind of argument, applied to different objects. That is greedy.
Where it bites
Pause and predict In Java, balloons are sorted by end with the comparator (a, b) -> a[1] - b[1]. One balloon ends at -2147483645 and another at 2147483647. Which one does the sort put first?
- Touching endpoints. Decide from the statement whether the intervals are closed or half-open, then choose
<or<=on purpose. In each line-ordering exercise above, one of the wrong lines differs in exactly this character. - The wrong sort key. Sort by start to merge intervals or to count how many overlap; sort by end to choose which to keep. Sorting by start when choosing keeps a long interval that starts early and blocks the others.
- The newer end instead of the max. If you set the block's end to the new interval's end, an interval lying inside the block shrinks it.
- Comparing with the previous input interval instead of the last merged block: after
[1, 10], [2, 3], the interval[5, 6]must be compared with 10, and 3 is the wrong number. - Returning sorted queries in the wrong order. When you sort the queries to answer them, store each answer at the query's original index.