Intervals and sweep line

Q: Why does sorting by start make one pass enough?

After the sort, every interval you have not read yet starts at or after the one you are holding. So an interval can only overlap the most recent one you kept: anything earlier either ended before that one did, or was already folded into it. That means you carry exactly one candidate, the last interval in the output, and you compare against it alone. Everything to its left is final and can never grow again.

Q: What is a sweep line, and when do I use it instead of merging?

A sweep line turns each interval into two events, plus one where it starts and minus one where it ends, sorts the events, and walks them keeping a running sum. That sum is how many intervals are open at that coordinate. Use it when the question is about how many are open at once, or about a value that changes at endpoints: rooms needed, maximum overlap, the skyline. Use the merge loop when the answer is a set of intervals rather than a count.

Q: A sweep line or a heap of end times: which should I write?

They compute the same thing. The sweep is shorter and has no data structure at all, so it is the one to write when the events can be built and sorted up front. The heap of end times keeps the intervals themselves, so use it when you have to know which intervals are open and not only how many, as in the skyline, or when intervals arrive one at a time and cannot all be sorted in advance.

Q: Why is merging intervals O(n log n) and not O(n)?

The pass itself is linear: each interval is read once and compared against one other interval. The sort in front of it costs O(n log n), and that dominates. So the honest answer in a round is n log n, dominated by the sort, and the follow-up worth naming is that an input already sorted by start, as in Insert Interval, drops the whole thing to O(n).

Sort the ranges by where they start. One pass is then enough, because the only interval a new one can still touch is the last one you kept.

Problems worked on this page, and more to practise

When do two intervals overlap?

Two intervals a and b overlap when a.start <= b.end and b.start <= a.end. Both halves are needed: one alone only says that a starts before b finishes. The open question is whether ends that merely touch count, so [1, 2] against [2, 3]. With <= they overlap and merge; with < they do not. Ask the interviewer which the problem means before you write the test, because both appear in real problems and the code differs by one character.

Why does sorting by start make one pass enough?

After the sort, every interval you have not read yet starts at or after the one you are holding. So an interval can only overlap the most recent one you kept: anything earlier either ended before that one did, or was already folded into it. That means you carry exactly one candidate, the last interval in the output, and you compare against it alone. Everything to its left is final and can never grow again.

What is a sweep line, and when do I use it instead of merging?

A sweep line turns each interval into two events, plus one where it starts and minus one where it ends, sorts the events, and walks them keeping a running sum. That sum is how many intervals are open at that coordinate. Use it when the question is about how many are open at once, or about a value that changes at endpoints: rooms needed, maximum overlap, the skyline. Use the merge loop when the answer is a set of intervals rather than a count.

A sweep line or a heap of end times: which should I write?

They compute the same thing. The sweep is shorter and has no data structure at all, so it is the one to write when the events can be built and sorted up front. The heap of end times keeps the intervals themselves, so use it when you have to know which intervals are open and not only how many, as in the skyline, or when intervals arrive one at a time and cannot all be sorted in advance.

Why is merging intervals O(n log n) and not O(n)?

The pass itself is linear: each interval is read once and compared against one other interval. The sort in front of it costs O(n log n), and that dominates. So the honest answer in a round is n log n, dominated by the sort, and the follow-up worth naming is that an input already sorted by start, as in Insert Interval, drops the whole thing to O(n).