Return the minimum number of rooms needed so that every meeting can happen.
Restating the Problem: You are given a list of meetings with start and end times. If two meetings overlap, they must be put into different rooms. You want to find out the absolute minimum number of rooms required to accommodate all meetings simultaneously.
Constraints to note: The number of meetings can be up to 10^4. O(n \log n) sorting approaches are ideal.
Edge cases: No meetings (returns 0). Meetings that end exactly when another begins (e.g., [1, 2] and [2, 3]) do not conflict and can share a room.
The naive approach is to use a list of "rooms" where each room contains a list of meetings it hosts. For every new meeting, you check each existing room to see if it can fit without overlapping. If it fits, you place it there; if it overlaps with all existing rooms, you create a new room. This takes O(n^2) time in the worst case (when all meetings overlap, you check O(n) rooms for each of the n meetings). This is too slow for large n.
The answer is the largest number of meetings happening at the same moment. You need one room per concurrent meeting, and no more, because a room is reusable the instant a meeting ends.
So the question becomes: what is the maximum overlap at any point in time?
There are two standard answers, and you should know both.
Forget which start belongs to which end. Treat starts and ends as separate events, sort all of them by time, and sweep:
a start adds one to the count of rooms in use;
an end subtracts one.
The answer is the highest the count ever reaches.
python
class Solution: def minMeetingRooms(self, intervals: List[List[int]]) -> int: starts = sorted(i[0] for i in intervals) # (1) ends = sorted(i[1] for i in intervals) # (2) rooms = best = 0 # (3) s = e = 0 # (4) while s < len(starts): # (5) if starts[s] < ends[e]: # (6) a meeting begins before any ends rooms += 1 s += 1 best = max(best, rooms) # (7) else: # (8) a meeting ends first — free a room rooms -= 1 e += 1 return best
ts
function minMeetingRooms(intervals: number[][]): number { const starts = intervals.map(i => i[0]).sort((a, b) => a - b); // (1) const ends = intervals.map(i => i[1]).sort((a, b) => a - b); // (2) let rooms = 0, best = 0, s = 0, e = 0; // (3) while (s < starts.length) { // (5) if (starts[s] < ends[e]) { rooms++; s++; best = Math.max(best, rooms); } // (6) else { rooms--; e++; } // (8) } return best;}
Separating the starts from the ends is the key move. It looks wrong, because you have thrown away which end belongs to which start. But that does not matter. You are only counting how many meetings are open at each moment, and for that the pairing is irrelevant.
starts[s] < ends[e] uses <, so a meeting ending exactly when another starts frees the room in time. That is the same convention as 4.27.4.
Line by line.
(1) All the start times, sorted.
(2) All the end times, sorted separately. We no longer know which end belongs to which start, and we do not need to. We only count how many meetings are running at each moment.
(3) rooms is how many meetings are running right now, and best is the most that were ever running at once.
(4) A pointer into each list.
(5) Keep going while some meeting has yet to start.
(6) The next thing to happen is a meeting starting, because the next start comes before the next end. One more room is busy. Using < means that when a meeting ends at the very moment another starts, the end is handled first, so the room is reused.
(7) Keep the highest count seen. That is the number of rooms needed.
(8) Otherwise the next thing to happen is a meeting ending. A room is freed.
The loop runs while starts remain. Once every meeting has begun, the count can only fall, so the maximum has already been seen.
Sort the meetings by start. Keep a min-heap of the end times of the meetings currently in rooms.
For each meeting: if the earliest-ending meeting has already finished, reuse its room by popping it. Then push this meeting's end. The heap's size is the number of rooms in use, and its maximum is the answer.
python
import heapqclass Solution: def minMeetingRooms(self, intervals: List[List[int]]) -> int: intervals.sort(key=lambda x: x[0]) # (9) heap = [] # (10) end times of busy rooms for start, end in intervals: # (11) if heap and heap[0] <= start: # (12) heapq.heappop(heap) # that room is free again heapq.heappush(heap, end) # (13) return len(heap) # (14)
Line by line.(9) Sort the meetings by start. (10) A min-heap of the end times of the rooms in use, so the room that frees up soonest is at the front. (11) Take each meeting in start order. (12) If the room that frees up soonest is free by the time this meeting starts, reuse it by removing its old end time. (13) This meeting now occupies a room, so add its end time. (14) The heap's size is the number of rooms ever needed.
Only one pop per meeting is needed, even if several rooms have freed up. If two rooms are free you only need one for this meeting, and the other stays available for later — the heap's size is still correct.
The final heap size is the answer, because the heap only ever shrinks when a room is genuinely reused, so its peak equals its final size.
The heap version reads more like the story — rooms with meetings in them — and it extends when you need to know which room each meeting used, since you can store room identifiers alongside the end times.
The sweep line is slightly faster and generalises further, and it is the one to reach for when the question is about counts rather than assignments.
This is the main idea to take away from the whole chapter.
Convert each interval into two events, sort all events by time, and sweep with a running count.
python
events = []for start, end in intervals: events.append((start, +1)) events.append((end, -1))events.sort() # ties: -1 before +1, so an ending frees a room first
The tie-break matters. At equal times you want the -1 processed first, so a meeting ending at 10 frees a room for one starting at 10. Sorting tuples does this automatically because -1 < +1.
It solves a large family:
Maximum concurrent anything — meetings, downloads, database connections, aircraft in a sector.
Car Pooling (LeetCode 1094) — passengers boarding and leaving, with a capacity check.
My Calendar II and III — counting double and triple bookings.
The skyline problem (LeetCode 218) — a sweep line with a heap of building heights.
Rate limiting and capacity planning in production systems, which is Chapter 11.3.
O(n \log n) time and O(n) space for both solutions.
Time Complexity:O(n \log n). Sorting the arrays (or using a heap) takes O(n \log n) time. The subsequent sweeping (or heap push/pops) takes O(n) time.
Space Complexity:O(n) extra space to store the separated start and end arrays (or the heap).
If the times were small whole numbers in a known range, you could use a difference array instead. Add 1 at each start and subtract 1 at each end, then take a running sum and find its maximum. That is O(n + T), where T is the time range. It is the bounded-values trick from 4.4.5. Name it as the improvement when times are, say, minutes in a day.
"Why can you separate starts from ends?" You are counting concurrency, and the pairing does not affect the count.
"What happens at equal times?" An end must be processed before a start, or a reusable room is missed.
"Why is the heap's size the answer?" It holds exactly the meetings currently occupying rooms.
"Why only one pop per meeting?" You only need one room for one meeting.
"What if you needed to know which room each meeting used?" Store room ids in the heap alongside the end times.
"What if the times were minutes in a day?" A difference array, O(n + 1440).
One thing to volunteer: name the sweep line and give one non-meeting use of it. It is the most transferable technique in the interval chapter, and interviewers notice when a candidate has a name for what they are doing.