Definition
- Peak concurrency – the minimum number of rooms equals the maximum number of meetings active at any single instant.
- Min-heap of end times – tracks the end time of each occupied room; the soonest-ending meeting is at the root.
- Free-then-occupy – before seating a new meeting, poll any room whose end time is at or before the new start; then offer the new end.
- Heap size = rooms – the heap size at any moment is the number of concurrent meetings; its maximum is the answer.
- Two-pointer alternative – separate and sort all starts and ends, walk both pointers, increment on starts and decrement on ends.
At the National Bank of India, Rajesh schedules customer advisory sessions throughout the day. He processes sessions in start-time order, keeping a tray of busy-until times. Before seating a new session he removes any room from the tray whose session has ended. Then he seats the new session. The largest the tray ever grows is the minimum number of rooms he needs.
Understanding the Concepts
What is the Minimum Meeting Rooms problem?
The problem gives a set of meetings, each with a start and end time, and asks for the minimum number of rooms needed so that no two overlapping meetings share a room. This is equivalent to finding the maximum number of meetings active at any single instant, because that peak is the moment when the most rooms are in use.
package com.bank.service;
import java.util.*;
public class MinMeetingRooms {
public int minMeetingRooms(int[][] meetings) {
if (meetings.length == 0) return 0;
Arrays.sort(meetings, Comparator.comparingInt(a -> a[0]));
PriorityQueue<Integer> heap = new PriorityQueue<>(); // min-heap of end times
heap.offer(meetings[0][1]);
for (int i = 1; i < meetings.length; i++) {
if (heap.peek() <= meetings[i][0]) {
heap.poll(); // room freed
}
heap.offer(meetings[i][1]); // occupy a room
}
return heap.size();
}
public static void main(String[] args) {
int[][] meetings = {{0,30},{5,10},{15,20}};
System.out.println("Rooms needed: " + new MinMeetingRooms().minMeetingRooms(meetings));
}
}
Rooms needed: 2
Why does the heap give the correct answer?
The min-heap holds the end time of each currently occupied room. Before seating a new meeting, we check the root: if the soonest-ending room finishes at or before the new meeting's start, that room is free and we poll it. Then we offer the new meeting's end time. Because we only free rooms that genuinely ended, the heap size at any moment equals the number of concurrent meetings. The maximum heap size over the entire run is the answer.
package com.bank.service;
import java.util.*;
public class HeapTrace {
public static void main(String[] args) {
int[][] meetings = {{0,30},{5,10},{15,20}};
Arrays.sort(meetings, Comparator.comparingInt(a -> a[0]));
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int[] m : meetings) {
if (!heap.isEmpty() && heap.peek() <= m[0]) {
System.out.println("Free room ending at " + heap.poll());
}
heap.offer(m[1]);
System.out.println("Seat [" + m[0] + "," + m[1] + "] heap size=" + heap.size());
}
System.out.println("Max rooms: " + heap.size());
}
}
Seat [0,30] heap size=1
Seat [5,10] heap size=2
Free room ending at 10
Seat [15,20] heap size=2
Max rooms: 2
What is the two-pointer sweep alternative?
Separate all start times and all end times into two sorted arrays. Walk a start pointer and an end pointer. When the next event is a start, increment a running room count and update the maximum. When the next event is an end, decrement the room count. The peak running count is the answer. This avoids the heap.
package com.bank.service;
import java.util.Arrays;
public class TwoPointerMeetingRooms {
public int minMeetingRooms(int[][] meetings) {
int n = meetings.length;
int[] starts = new int[n];
int[] ends = new int[n];
for (int i = 0; i < n; i++) {
starts[i] = meetings[i][0];
ends[i] = meetings[i][1];
}
Arrays.sort(starts);
Arrays.sort(ends);
int rooms = 0, maxRooms = 0;
int s = 0, e = 0;
while (s < n) {
if (starts[s] < ends[e]) {
rooms++;
maxRooms = Math.max(maxRooms, rooms);
s++;
} else {
rooms--;
e++;
}
}
return maxRooms;
}
public static void main(String[] args) {
int[][] meetings = {{0,30},{5,10},{15,20}};
System.out.println("Rooms (two-pointer): "
+ new TwoPointerMeetingRooms().minMeetingRooms(meetings));
}
}
Rooms (two-pointer): 2
How does the tie-handling work?
When a meeting ends exactly as another starts, whether they can share a room depends on the domain. Using <= in heap.peek() <= start means a room freed at time 10 can host a meeting starting at 10 (back-to-back reuse). Using < means the room is still occupied at 10 and a new room is needed.
package com.bank.service;
public class TieHandling {
public static void main(String[] args) {
// Meeting A: [0, 10], Meeting B: [10, 20]
// <= : room freed at 10, B starts at 10 => same room (1 room)
// < : room still busy at 10 => need 2 rooms
System.out.println("<= (back-to-back reuse): 1 room for [0,10] and [10,20]");
System.out.println("< (no reuse at exact end): 2 rooms");
}
}
How is this different from Merge Intervals?
| Feature | Merge Intervals | Meeting Rooms |
|---|---|---|
| Goal | merge overlapping intervals | count peak overlap |
| Output | merged interval list | integer (room count) |
| Technique | sort + sweep + extend | sort + heap or two-pointer |
| Key insight | max-end rule | min rooms = max overlap |
package com.bank.service;
public class MergeVsMeetingRooms {
public static void main(String[] args) {
System.out.println("Merge: combine overlapping, return merged list.");
System.out.println("Meeting Rooms: count peak overlap, return integer.");
}
}
What are the edge cases?
Edge cases include no meetings (0 rooms), one meeting (1 room), all meetings at the same time (n rooms), and no overlapping meetings (1 room).
package com.bank.service;
public class MeetingRoomEdgeCases {
public static void main(String[] args) {
MinMeetingRooms solver = new MinMeetingRooms();
System.out.println("No meetings: " + solver.minMeetingRooms(new int[][]{}));
System.out.println("One meeting: " + solver.minMeetingRooms(new int[][]{{0,10}}));
System.out.println("All overlap: " + solver.minMeetingRooms(
new int[][]{{0,10},{0,10},{0,10}}));
System.out.println("Sequential: " + solver.minMeetingRooms(
new int[][]{{0,5},{5,10},{10,15}}));
}
}
No meetings: 0
One meeting: 1
All overlap: 3
Sequential: 1
What are common mistakes?
The most common mistake is not sorting the meetings by start time before processing. Another mistake is freeing multiple rooms in one step instead of just the one whose end time is earliest.
Wrong code:
// WRONG: not sorted, processes meetings in arbitrary order
for (int[] m : meetings) {
heap.offer(m[1]);
}
Correct code:
// CORRECT: sort first, then free-and-occupy
Arrays.sort(meetings, Comparator.comparingInt(a -> a[0]));
for (int[] m : meetings) {
if (!heap.isEmpty() && heap.peek() <= m[0]) heap.poll();
heap.offer(m[1]);
}
What should a senior engineer know?
A senior engineer knows that "minimum rooms equals maximum overlap" is the key conceptual leap. They also know this exact model applies to CPU thread scheduling, connection pool sizing, airport gate assignment, and any resource allocation problem about peak simultaneous demand. Both the heap and two-pointer approaches run in O(n log n), and the choice depends on whether subsequent operations need the individual room assignments (heap) or just the count (two-pointer).
package com.bank.service;
public class SeniorMeetingRoomNotes {
public static void main(String[] args) {
System.out.println("Senior insights:");
System.out.println(" min rooms = max overlap (key insight).");
System.out.println(" Applies: CPU scheduling, connection pools, gate assignment.");
System.out.println(" Heap: O(n log n), gives room assignments.");
System.out.println(" Two-pointer: O(n log n), gives count only.");
}
}
Visual Overview
Meeting Rooms: Heap Processing
Meetings (sorted): [0,30], [5,10], [15,20]
Step 1: Seat [0,30]
Heap: [30]
Rooms: 1
Step 2: Seat [5,10]
heap.peek()=30 > 5 => no room freed
Heap: [10, 30]
Rooms: 2 ← peak
Step 3: Seat [15,20]
heap.peek()=10 <= 15 => free room ending at 10
Heap: [30]
Offer 20: Heap: [20, 30]
Rooms: 2
Answer: 2 rooms
Timeline view:
0 5 10 15 20 25 30
|============================| Room 1: [0,30]
|====| Room 2: [5,10]
|====| Room 2: [15,20] (reused)
Peak overlap at t=5: 2 meetings active
Key Takeaway
The minimum number of meeting rooms equals the maximum number of meetings that overlap at any single instant. This reframing from "scheduling" to "peak concurrency" is the key conceptual leap that makes the problem tractable.
The heap approach sorts meetings by start time and uses a min-heap of end times. Before seating each new meeting, poll any room whose end time is at or before the new start. Then offer the new meeting's end time. The heap size at any moment equals the concurrent meetings, and the maximum size is the answer. The two-pointer alternative separates and sorts starts and ends, then walks both, tracking a running room count.
The tie-handling decision matters: using less-than-or-equal allows back-to-back reuse (a room freed at 10 hosts a meeting starting at 10), while strict less-than requires a separate room. This is a domain choice, not a coding choice.
At National Bank of India, Rajesh uses this to provision advisory rooms across a day of customer bookings. The same model applies to connection pool sizing, CPU thread scheduling, and airport gate assignment: any resource allocation problem about peak simultaneous demand is this problem in disguise.
Remember one sentence: sort by start, use a min-heap of end times to free finished rooms, and the peak heap size is the minimum number of rooms.
---