Meeting Rooms II — Step-by-Step Visualization

Algorithm Pattern

Two Pointers or Priority Queue

Key Idea

We need to find the maximum number of concurrent meetings at any point in time. We can treat all 'starts' as +1 room and all 'ends' as -1 room. By sorting all start times and end times separately, we can use two pointers to simulate time moving forward. Whenever a meeting starts, we increment our 'rooms' count; whenever a meeting ends (at or before the current start time), we decrement 'rooms'.

Step-by-Step Approach

1. Create two sorted arrays: `start` times and `end` times.
2. Initialize `count = 0`, `res = 0`, and pointers `s = 0, e = 0`.
3. While `s < len(intervals)`:
4. If `start[s] < end[e]`:
5. A new meeting is starting before the earliest one ends. `count += 1`, `s += 1`.
6. Else:
7. A meeting has ended. `count -= 1`, `e += 1`.
8. Update `res = max(res, count)`.
9. Return `res`.

Common Gotchas

• If a meeting ends at the same time another starts (e.g., [0,10] and [10,20]), it is NOT an overlap. Sorting the end times correctly handles this if we use `<` instead of `<=`.