Meeting Room Scheduling
You'll learn: How to calculate the minimum number of meeting rooms needed using a greedy sorting approach with overlap tracking.
The Problem
Imagine you're managing a conference center with multiple meeting rooms. You receive a list of meeting requests, each with a start and end time. Your job: determine the minimum number of rooms needed so no meetings overlap in the same room.
The Greedy Approach
The key insight is that the maximum number of overlapping meetings at any point in time equals the minimum rooms needed.
Here's how the greedy algorithm works:
Step 1: Separate and Sort Events
Split each meeting into two events: a "start" and an "end." Sort all events by time. When times tie, process "end" events before "start" events (freeing a room before claiming a new one).
Step 2: Track Active Meetings
Walk through the sorted events with a counter:
- When you encounter a start event, increment the counter (one more active meeting)
- When you encounter an end event, decrement the counter (one meeting finished)
Step 3: Record the Peak
The maximum value your counter reaches is your answer—that's when the most meetings overlapped.
Example Walkthrough
Meetings: [1,4], [2,5], [3,6]
Events sorted: start(1), start(2), start(3), end(4), end(5), end(6)
Counter: 0 → 1 → 2 → 3 → 2 → 1 → 0
Maximum = 3 rooms needed
This greedy method works because we're making the locally optimal choice (processing events chronologically) which leads to the globally optimal solution.
Key Takeaway: Sort meeting intervals as separate start/end events, then sweep through them with a counter to find the maximum simultaneous meetings—that's your minimum room requirement.