Minimum meeting rooms.

Approach

The number of rooms you need is the largest number of meetings in progress at the same time. That count only changes at start and end times, so sort the start times and the end times separately and sweep through them. Each start needs a room. If the earliest end time you haven't used yet is at or before that start, that meeting has finished and its room is free, so move past that end time and reuse the room. Otherwise, every room is busy and you open a new one.

Sorting the starts and ends separately breaks the link between each meeting's start and end, but that's fine. Only the number of meetings that have started and ended by each moment matters, not which meeting is which.

Steps

1. Sort the start times and the end times into two separate lists.
2. Set rooms = 0 and point j at the first end time.
3. For each start time, if it's at or after ends[j], move j forward to reuse that room. Otherwise, add one to rooms.
4. Return rooms.

Complexity

• Time: O(n log n), for the two sorts.
• Space: O(n), for the two lists.

Common mistakes

• Opening a new room when a meeting starts at the exact moment another ends. Use >= so the freed room is reused.
• Sorting meetings by start time and comparing each one only with the previous meeting. A room can free up from any earlier meeting, not just the most recent one.