Intervals
Sweeping through time
Stop thinking about intervals. Think about the moments things start and stop, in order.
Key idea
The reframe
Questions about how many intervals are active at once are awkward to answer interval by interval, because the answer belongs to a moment rather than to any one interval.
So change what you iterate over. Each interval becomes two events: something begins, and later something ends. Sort all the events by time and walk them, keeping a running count that goes up on a start and down on an end.
The running count at any point is exactly how many intervals are active there, and every question about concurrency is a question about that count.
Why it works
Why ends must be processed before starts
When one interval ends at exactly the moment another begins, they are not concurrent, so the count must dip before it rises. Sorting the pairs handles this without any extra code: at equal times, -1 sorts before +1 because -1 is the smaller number.
That is a happy accident of the encoding, and it is worth understanding rather than relying on. If your problem treats touching as concurrent, you need ends to sort after starts, which means encoding them the other way round or sorting with an explicit key.
The two-list variant
The same sweep is often written without building an event list, by sorting starts and ends into two separate arrays and walking them with two indexes. Whichever time comes next decides whether the count rises or falls.
It avoids allocating pairs and reads well once you have seen it. The event-list version generalizes better, because an event can carry extra information such as which interval it belongs to.
The walk itself is the same whatever you are counting. Below it records, for each start, how many intervals had already finished by then.
Gotcha
Sorting the two lists independently is not a bug
Splitting starts from ends destroys the pairing, and that looks alarming. It does not matter, because the count only asks how many things have begun and how many have finished by a given moment, never which specific interval each event belonged to.
If the question does need to know which interval, the event-list form is required. Choosing between the two is about what the answer needs, not about which is cleverer.
Cost
Cost
Building the events is O(n), sorting them is O(n log n), and the sweep is O(n). The sort dominates, so O(n log n) time and O(n) space.
There is no faster general answer, since a comparison sort of the times is unavoidable when times are arbitrary. If times were small bounded integers you could bucket them, which is the Unit 1 counting-sort idea, and that is a genuinely good thing to mention as a follow-up.
One interval problem is still missing
There is a sixth problem in this family that asks, for each of many queries, the size of the smallest interval covering it. It needs a structure that can hand you the smallest thing currently available, which is a heap, so it waits until Unit 9.
The sweep you just learned is half of that solution. When you meet it there, the other half will be the only new part.
Sweep drills
build_events turns intervals into a sorted event list of (time, change) pairs with ends before starts at equal times. time_with_at_least returns the total time during which at least k intervals are active. count_overlapping_pairs returns how many pairs of intervals overlap at all.
Tests
data = [[0, 30], [5, 10], [15, 20]] print(build_events([[1, 3], [3, 5]])) print(time_with_at_least(data, 1), time_with_at_least(data, 2), time_with_at_least(data, 3)) print(count_overlapping_pairs(data), count_overlapping_pairs([]), count_overlapping_pairs([[1, 2], [1, 2], [1, 2]])) print(count_overlapping_pairs([[1, 3], [3, 5]]))
Output
Run the tests when you are ready.
Meeting Rooms Ii
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.