#253 Meeting Rooms II
frequently reported atNetflixByteDance / TikTokAtlassianOracleBloombergApple
the problem
In plain words
Each meeting is [start, end). Return the minimum number of rooms needed to hold all of them. A room freed at 10 can host a meeting that starts at 10.
in intervals = [[0,30],[5,10],[15,20]]
out 2
[0,30] needs its own room; [5,10] and [15,20] can share the other.
in intervals = [[7,10],[2,4]]
out 1
- 1 ≤ intervals.length ≤ 10⁴
- 0 ≤ start < end ≤ 10⁶
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code right here. Stuck for 20 minutes? Open one hint at a time.
This one is LeetCode Premium. You don't need a subscription: solve it right here. The free alternative linked above is the closest free practice; its label says how close it is.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternGreedy with a heapSweep line & difference array
The answer is the largest number of meetings running at the same moment. Track the rooms' end times; the earliest one tells you whether a room is free.
solutions
From brute force to optimal
The peak always happens at some meeting's start. For each start, count the meetings running then.
- For each meeting m, count meetings with start ≤ m.start < end.
- Return the maximum count.
n starts × n meetings.
Counters only.
class Solution { public int minMeetingRooms(int[][] intervals) { int best = 0; for (int[] m : intervals) { // the peak always happens at some start time int busy = 0; for (int[] other : intervals) { if (other[0] <= m[0] && m[0] < other[1]) busy++; // [start, end) contains m's start } best = Math.max(best, busy); } return best; }}Sort by start. The heap holds one end time per busy room. If the earliest end ≤ the new start, reuse that room.
- Sort by start.
- If heap.peek() ≤ start, poll it (room freed).
- Offer this meeting's end. The final heap size is the answer.
The sort, then at most one poll and one offer (O(log n) each) per meeting.
The heap can hold every meeting.
class Solution { public int minMeetingRooms(int[][] intervals) { Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); // by start PriorityQueue<Integer> ends = new PriorityQueue<>(); // end times of rooms in use for (int[] m : intervals) { if (!ends.isEmpty() && ends.peek() <= m[0]) { // earliest-free room is free by now ends.poll(); // reuse it } ends.offer(m[1]); // this meeting occupies a room until m[1] } return ends.size(); // rooms ever needed at once }}Dry run with rooms
Sort starts and ends separately. A start before the earliest unused end needs a new room; otherwise it takes over a freed one.
- starts[], ends[] sorted.
- For each start: if start < ends[e], rooms++; else e++.
- Return rooms.
Two sorts + one linear pass.
Two arrays.
class Solution { public int minMeetingRooms(int[][] intervals) { int n = intervals.length; int[] starts = new int[n], ends = new int[n]; for (int i = 0; i < n; i++) { starts[i] = intervals[i][0]; ends[i] = intervals[i][1]; } Arrays.sort(starts); Arrays.sort(ends); int rooms = 0, e = 0; for (int s = 0; s < n; s++) { if (starts[s] < ends[e]) { // nobody has left yet rooms++; // open a new room } else { e++; // someone left: take over their room } } return rooms; }}Sweep line
in the room
How to say it in the interview
talk track
- Reframe: "minimum rooms = maximum overlap at any instant."
- Clarify the boundary: does a meeting ending at 10 free its room for one starting at 10? (Yes, so use
<=in the heap check.) - Give the heap solution, then mention the sweep line as a lighter alternative.
traps
- Sorting the heap version by end instead of start.
- Using
<instead of<=when reusing a room, so back-to-back meetings get two rooms.
what they ask next
Follow-ups
Which room does each meeting get (LC 2402 Meeting Rooms III)?
Use two heaps: free room ids, and busy rooms ordered by (end, id). Delay a meeting when no room is free.
Can one person attend everything?
That's Meeting Rooms (LC 252) earlier in this chapter: sort by start and check neighbours.
before you submit
Edge cases to test
- Back-to-back [1,5] and [5,10] → 1 room.
- All meetings nested inside each other → n rooms.
- Several meetings with the same start → each needs its own room.
practise next
Similar problems
- #252Meeting RoomsEasyin IntervalsLeetCode Premium
- #1094Car PoolingMediumin Intervals
- #621Task SchedulerMediumin Heaps