Trigger: how many are live at once, or the running value at each point. Turn each interval into a +1 at its start and a -1 at its end, sort the events, and read the running total. Which question is it asking?
Define the depth at a time t as how many intervals contain t:
depth = lambda t: sum(1 for s, e in intervals if s <= t < e)
Minimum meeting rooms is exactly max(depth(t) for all t), because at the busiest instant every one of those meetings is mid-flight and each needs its own room, and at no instant does anything need more. So the whole problem is: find the maximum of depth over the timeline. The timeline is continuous, so you cannot try every t.
depth is a step function. It can only change at a time where an interval starts or ends, because those are the only moments an interval enters or leaves the "contains t" set. Between two consecutive endpoints nothing changes, so the whole continuous timeline collapses to the 2n endpoints, and the maximum is guaranteed to be attained at one of them.
That is the sweep line: walk the endpoints left to right and maintain depth as you go, rather than recomputing it from scratch at each one.
Recomputing depth(t) at each of the 2n endpoints would be O(n²). But crossing an endpoint changes depth by exactly one, and you already know the direction: a start adds an interval, an end removes one. So tag each endpoint with its delta - +1 for a start, -1 for an end - sort the tagged endpoints by time, and depth becomes a running total that costs O(1) per event.
def min_rooms(intervals):
events = []
for start, end in intervals:
events.append((start, 1)) # an interval opens here
events.append((end, -1)) # an interval closes here
events.sort(key=lambda e: (e[0], e[1])) # by time; at equal times, -1 before +1
concurrent = peak = 0
for time, delta in events:
concurrent += delta # concurrent == depth just after `time`
peak = max(peak, concurrent)
return peak
concurrent is the depth immediately after the current event, and peak is the running maximum, so the loop's invariant is exactly "the answer so far." Everything is O(n log n) for the sort plus O(n) for the sweep, and O(n) space for the event list.
GOTCHASort ties: why the key is (e[0], e[1]) and not just e[0]
The tuple key sorts by time first and by delta second, and -1 < 1, so when a close and an open land on the same t the close is processed first. A meeting that ends at 10:00 frees its room in time for one starting at 10:00, so those two should count as one room, not two. Sorting on e[0] alone leaves the tie order up to which endpoint happened to be appended first, which makes the answer depend on input order.
This matches the strict < in the depth definition above: an interval [s, e] contains s but not e.
2406 is the exception: its intervals are inclusive on both ends, so touching ones still share a point and need separate groups. Its end event fires at b+1 instead of b, so a touching pair overlaps for one tick.
Meetings [0,30], [5,10] and [15,20]. Depth rises at each start and falls at each end, and its maximum over the whole timeline is 2 - so two rooms. Note the maximum is reached twice, at t=5 and again at t=15.
Step it yourself - the sweep line moves one event at a time, bars light up while they are open, and the depth chart draws itself only as far as the sweep has reached:
visualization loads as you reach it
Python
def min_rooms(intervals):
events = []
for start, end in intervals:
events.append((start, 1))
events.append((end, -1))
events.sort(key=lambda e: (e[0], e[1]))
concurrent = peak = 0
for time, delta in events:
concurrent += delta
peak = max(peak, concurrent)
return peak
Two other shapes compute the exact same peak, and are worth recognizing since solutions online use all three interchangeably:
Approach
What it tracks
When it reads clearer
Sweep line (events)
a running +1/-1 total over sorted event times
the answer is framed as "concurrency at a point", or you need every intermediate count, not just the peak
Min-heap of end times
the soonest-freeing room, popped whenever it is free before the next meeting starts
the answer is framed as "rooms" or "resources" - it's the most direct translation of the real-world allocation
Two sorted pointers (starts / ends)
a start-pointer and an end-pointer racing through two separately-sorted arrays
you only have the raw intervals and want to avoid building a heap or an explicit event list at all
import heapq
def min_rooms_heap(intervals):
intervals.sort(key=lambda x: x[0])
heap = [] # end times of rooms currently in use
for start, end in intervals:
if heap and heap[0] <= start:
heapq.heappop(heap) # the earliest-freeing room is free by `start` - reuse it
heapq.heappush(heap, end)
return len(heap) # rooms still occupied = rooms needed
def min_rooms_two_pointers(intervals):
starts = sorted(s for s, _ in intervals)
ends = sorted(e for _, e in intervals)
rooms = peak = 0
s = e = 0
while s < len(starts):
if starts[s] < ends[e]: # a meeting starts before the earliest one ends
rooms += 1
peak = max(peak, rooms)
s += 1
else: # the earliest meeting ends first - free a room
rooms -= 1
e += 1
return peak
The heap version never grows past the number of rooms currently in use, so it's the tightest of the three on space; the two-pointer version needs no heap or event tuples at all, just two sorted arrays - both compute the same peak as the event sweep above. The heap version is also the first step toward problems that ask which interval to serve next, not just how many are live - see admit, expire, serve.
The sweep above, applied: the running total is how many intervals are active at that instant, and the maximum it ever reaches is the answer whenever the question is "how many at once".
253, 1094 and 2406 also have a min-heap solution. It computes the same peak but also knows which intervals are open and which frees up first, so it extends to deciding which one to serve: admit / expire / serve.
Same +1/-1 events, but the peak is not enough: the running value is needed at every position, at every stretch between event points, or at a set of query points. When the coordinates are small indices this is a difference array; when they are sparse, sort the event points (and the queries) and read the running value as the sweep passes each one.
