Minimum Meeting Rooms
Mahabharata — Dhritarashtra's War Council — The Minimum Number of Chambers for All Meetings
एककाले यावन्तः सभायां तिष्ठन्ति। तावन्त्यः कक्षाः आवश्यकाः — नाधिकं न न्यूनम्॥
*As many as are simultaneously present in the council — that many chambers are required. Neither more nor less.*
The Story
Dhritarashtra needed to hold war councils simultaneously. Given n meetings with their start and end times, what is the minimum number of meeting rooms required so all meetings can happen?
Sahadeva proposed the Event Sweep approach: "Create events: +1 for every meeting START, -1 for every meeting END. Sort all events by time (break ties: end before start — a room freed at time t can host a meeting starting at t). Sweep through: maintain a running count. The maximum running count is the answer."
For `meetings = [[9,10],[4,9],[4,17]]`: Events: (4,+1),(4,+1),(9,+1),(9,-1),(10,-1),(17,-1) Sort with end-before-start tie-break: (4,+1),(4,+1),(9,-1),(9,+1),(10,-1),(17,-1)
Sweep: 0→1→2→1→2→1→0. Maximum = 2.
Answer: 2 meeting rooms needed.
"Wait," Sahadeva said. "The tie-breaking matters. At time 9: meeting [4,9] ends (-1) and [9,10] starts (+1). If we process end first: count goes 2→1→2. If we process start first: 2→3 then→2. Since one room is freed exactly when another meeting starts, end-before-start correctly shows we only need 2 rooms."
Alternative: Min-heap tracking end times. Sort by start. For each meeting, if earliest end (heap top) <= current start, that room is free — reuse it (pop). Then push current end. Heap size at the end = rooms needed.
Both approaches give the same answer.
The Coordinator's First Instinct
For each time point, count how many meetings are active. The maximum is the answer. O(max_time × n).
public int minMeetingRoomsBruteForce(int[][] intervals) {
if (intervals.length == 0) return 0;
int maxTime = 0;
for (int[] iv : intervals) maxTime = Math.max(maxTime, iv[1]);
int maxRooms = 0;
for (int t = 0; t <= maxTime; t++) {
int count = 0;
for (int[] iv : intervals) if (iv[0] <= t && t < iv[1]) count++;
maxRooms = Math.max(maxRooms, count);
}
return maxRooms;
}Sahadeva's Sweep Wisdom
public int minMeetingRooms(int[][] intervals) {
int n = intervals.length;
int[][] events = new int[n * 2][2];
int idx = 0;
for (int[] iv : intervals) {
events[idx++] = new int[]{iv[0], 1}; // start: +1
events[idx++] = new int[]{iv[1], -1}; // end: -1
}
// Sort: by time; ties: end (-1) before start (+1)
Arrays.sort(events, (a, b) -> a[0] != b[0] ? a[0]-b[0] : a[1]-b[1]);
int rooms = 0, maxRooms = 0;
for (int[] e : events) {
rooms += e[1];
maxRooms = Math.max(maxRooms, rooms);
}
return maxRooms;
}Step-by-Step Walkthrough
[[7,10],[2,4]] Events: (2,+1),(4,-1),(7,+1),(10,-1) Sweep: 0→1→0→1→0. Max=1. Return 1 ✅ (meetings don't overlap — only 1 room needed)
Deep Insight
**End-before-start tie-breaking:** If a meeting ends at t=9 and another starts at t=9, the room can be reused. Processing -1 before +1 at the same time reflects this: count goes down before going up, keeping the maximum lower (correctly).
**Min-heap alternative:** Sort by start. Min-heap of end times. For each meeting: if heap.peek() <= start → pop (reuse room). Push current.end. Heap size at end = rooms needed.
**Both approaches:** Event sweep is elegant; min-heap is intuitive. Same complexity.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n × max_time) | O(1) | Scan all time points |
| Optimal | O(n log n) | O(n) | Sort 2n events + linear sweep |
Pattern Recognition
✅ Minimum meeting rooms = peak simultaneous meetings ✅ Event sweep: +1 start, -1 end, sort by time ✅ Tie-break: end events before start events ✅ Track maximum running count **LeetCode Trigger Phrases:** → "minimum meeting rooms" → "minimum number of intervals to cover" at same time → "peak concurrent" + intervals
Bhagavad Gita 6.19
यथा दीपो निवातस्थो नेङ्गते सोपमा स्मृता। योगिनो यतचित्तस्य युञ्जतो योगमात्मनः॥
As a lamp in a windless place does not flicker — such is said to be the likeness of the yogi with controlled mind, practicing yoga of the Self.
Connection: The meeting room count rises and falls like the flame of awareness — peaking when most minds converge simultaneously, subsiding when they depart. The event sweep finds this peak with the same steady attention the Gita prescribes: not rushing to conclusions, but observing each moment of arrival and departure until the true maximum reveals itself.