Meeting Rooms II — Sweep Line on Start/End Times
Separate start and end times, sort both, and sweep to find the maximum number of concurrent meetings.
Problem Statement
Given meeting time intervals, determine the minimum number of conference rooms required.
Why This Problem Matters
- Interval partitioning question testing sweep-line or min-heap skills.
- Relates directly to real-world scheduling challenges.
- Builds intuition for concurrency counting problems.
Thought Process
Sort start and end times separately
Sorting allows linear sweep comparing upcoming meetings with earliest ending ones.
Use two pointers
When a meeting starts before the earliest end finishes, increment rooms; otherwise free a room by advancing end pointer.
Track peak usage
Maintain current rooms in use and update maxRooms as the answer.
Step-by-Step Reasoning
- Extract arrays of start and end times and sort both.
- Initialise pointers i = 0 (starts) and j = 0 (ends), rooms = 0, maxRooms = 0.
- While i < n, if starts[i] < ends[j], increment rooms and i; else decrement rooms and j++.
- Update maxRooms each iteration; return it.
Dry Run
[[0,30],[5,10],[15,20]]
rooms peaks at 2 because first meeting overlaps with others.
[[7,10],[2,4]]
rooms never exceeds 1 as meetings do not overlap.
Complexity Analysis
Time
O(n log n)
Space
O(n)
Why
Sorting dominates; arrays of size n hold start and end times.
Annotated Solution
import java.util.Arrays;
public class MeetingRoomsII {
public int minMeetingRooms(int[][] intervals) {
if (intervals.length == 0) {
return 0;
}
int n = intervals.length;
int[] starts = new int[n];
int[] ends = new int[n];
for (int i = 0; i < n; i += 1) {
starts[i] = intervals[i][0];
ends[i] = intervals[i][1];
}
Arrays.sort(starts);
Arrays.sort(ends);
int rooms = 0;
int maxRooms = 0;
int i = 0;
int j = 0;
while (i < n) {
if (starts[i] < ends[j]) {
rooms += 1;
maxRooms = Math.max(maxRooms, rooms);
i += 1;
} else {
rooms -= 1;
j += 1;
}
}
return maxRooms;
}
}Two-pointer sweep counts concurrent meetings; when a meeting ends, a room frees up for the next start time.
Common Pitfalls
- Using <= comparison can free rooms too early; stick with < so back-to-back meetings reuse rooms.
- Min-heap approach requires removing ended meetings; forgetting to poll leads to wrong counts.
- Not handling empty input returning zero rooms.
Follow-Up Questions
- How would you list the actual room assignments?
- Can you handle online (streaming) meeting requests?