Meeting Rooms II
Problem
intervals[i] = [start, end], each occupying the half-open
range [start, end), return the minimum number of conference rooms
needed so that no two meetings sharing a room overlap. A room freed at time
t can host a meeting starting at t.intervals = [[0,30],[5,10],[15,20]]Output2intervals = [[7,10],[2,4]]Output1intervals = [[1,5],[2,6],[3,7]]Output31 ≤ intervals.length ≤ 104 · 0 ≤ start < end ≤ 106
Try it yourself
class Solution {
public int minMeetingRooms(int[][] intervals) {
}
}
Instinct See [start, end] pairs, meetings, bookings or the word "overlap"? Sort by an endpoint, then sweep left to right carrying one running fact.
Memory hack Sort, then sweep - start time to merge, end time to choose, +1/-1 events to count the crowd.
Open the Intervals & Line Sweep guide →Approaches
Brute ForceCount Overlaps at Every Start
O(n2)Space O(1)The number of active meetings only rises at a start time, so the peak is
reached at some meeting's start. For each start s, count meetings
with start ≤ s < end and keep the maximum.
public int minMeetingRooms(int[][] intervals) { int best = 0; for (int[] m : intervals) { int busy = 0; // meetings running at the instant m starts for (int[] o : intervals) { if (o[0] <= m[0] && m[0] < o[1]) busy++; } best = Math.max(best, busy); } return best; }
No sorting needed and easy to trust, but quadratic.
BetterSort by Start + Min-Heap of End Times
O(n log n)Space O(n)Process meetings by start time and keep a min-heap holding the end time of every room in use. If the earliest-ending room is free by the time the next meeting starts, reuse it (pop); either way push the new end. The heap never shrinks below the rooms truly needed, so its final size is the answer.
public int minMeetingRooms(int[][] intervals) { Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); PriorityQueue<Integer> roomEnds = new PriorityQueue<>(); for (int[] m : intervals) { if (!roomEnds.isEmpty() && roomEnds.peek() <= m[0]) { roomEnds.poll(); // that room is free again } roomEnds.offer(m[1]); } return roomEnds.size(); }
Optimal complexity and models real rooms, but needs a heap.
OptimalTwo Sorted Arrays (Chronological Sweep)
O(n log n)Space O(n)Sort starts and ends independently. Sweep the starts; pointer
e marks the earliest end not yet used. If a start is at or after
ends[e], some meeting has finished and its room is reused
(e++); otherwise a new room is opened.
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]) { e++; // a meeting ended: reuse its room } else { rooms++; // everyone is still busy: open a room } } return rooms; }
Dry runintervals = [[0,30],[5,10],[15,20]]
- starts0515ends = [10,20,30]
- s=00s5150 < 10: rooms=1
- s=105s155 < 10: rooms=2
- s=20515s15 ≥ 10: reuse, e=1 ✔
Same Big-O as the heap, but just two sorts and two pointers.
>= when comparing a start with an end: a room freed at
t is available at t.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Count Overlaps at Every Start | O(n2) | O(1) |
| Better | Sort by Start + Min-Heap of End Times | O(n log n) | O(n) |
| Optimal | Two Sorted Arrays (Chronological Sweep) | O(n log n) | O(n) |
- Using
>instead of>=— back-to-back meetings get two rooms. - Sorting by end time in the heap approach — it must process meetings by start.
- Returning the number of overlapping pairs instead of the peak concurrency.
- State the reduction: rooms needed = maximum concurrent meetings.
- Show the heap version first; it maps directly to “assign real rooms”.
- Mention a difference-array sweep when times are small integers.