Meeting Rooms II

Find the fewest rooms for a set of meetings: take meetings by start time and keep a min-heap of the times each room frees up.

The idea

Hand out rooms in the order meetings start. When a meeting starts, the only room worth checking is the one that frees up earliest: if even that one is still busy, every room is, and a new room must open. A min-heap of end times answers "which room frees first?" in O(log n), and its size is the number of rooms opened.

Code

public static int MinMeetingRooms(int[][] intervals) {
    Array.Sort(intervals, (x, y) => x[0].CompareTo(y[0]));
    var ends = new PriorityQueue<int, int>(); // one entry per room: when it frees up
    foreach (var m in intervals) {
        if (ends.Count > 0 && ends.Peek() <= m[0])
            ends.Dequeue(); // that room is free again: reuse it
        ends.Enqueue(m[1], m[1]); // the room is busy until m ends
    }
    return ends.Count;
}

Tips

• A meeting that starts exactly when another ends can reuse its room, hence ends.Peek() <= start.
• Equivalent two-array sweep: sort starts and ends separately; each start either reuses a room (start >= the earliest unused end) or opens a new one.
• Only one room is popped per meeting, so the heap size can only grow or stay put: it ends up as the peak number of rooms in use at once.

In the .NET library

PriorityQueue<TElement, TPriority> (.NET 6+) is a min-heap on the priority; here the end time is both the element and its priority. Peek and Dequeue throw on an empty queue, so check Count first.