Meeting Rooms II
Determine the minimum number of conference rooms required to schedule all meetings using the Sweep Line algorithm.
Meeting Rooms
Active Rooms: 0
Max Needed: 0
Ready
Controls
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
The Core Idea: Instead of checking every minute of the day to see how many meetings are happening, we only care about the moments when the number of active meetings changes.
These moments are the Start and End times of the meetings.
Imagine a vertical line sweeping across the timeline. Every time it hits a Start, we need a room (+1). Every time it hits an End, a room becomes free (-1).
Concept
Sweep Line (Chronological Ordering):
- Events: Deconstruct every interval
[start, end]into two separate events:(start, +1)and(end, -1). - Sorting: Sort all events by time. If times are equal, process the End event first (to free up the room before re-allocating it).
- Scanning: Iterate through the sorted events, maintaining a running sum of active meetings. The maximum value of this sum is the answer.
How it Works
The visualizer effectively sorts the start and end times.
- Timeline: Meetings are placed on a timeline.
- Scan: A vertical line moves from left to right.
- Counter: As the line passes a 'Start', the 'Active Rooms' counter increases. As it passes an 'End', it decreases.
- Result: The peak value of the counter is recorded as the minimum rooms required.
Step-by-Step Breakdown
1. Separate: Create an array of start times and an array of end times.
2. Sort: Sort both arrays.
3. Two Pointers: Use s_ptr for starts and e_ptr for ends.
4. Iterate:
- If start[s_ptr] < end[e_ptr]: A meeting starts. rooms++. s_ptr++.
- Else: A meeting ends. rooms-- (or reuse). e_ptr++.
5. Track Max: Keep track of the maximum rooms needed at any point.
When to Use
- Finding maximum concurrency/overlap in intervals.
- Resource allocation problems (rooms, platforms, bandwidth).
- "Merge Intervals" variations.
When NOT to Use
- When you need to select a subset of non-overlapping intervals (Activity Selection / Greedy).
- When intervals have weights/values and you want to maximize value (Weighted Interval Scheduling / DP).
How to Identify
"Minimum resources required", "Maximum simultaneous events", "Find the point of maximum overlap".
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.