Meeting Rooms II

Problem

Given start/end times for meetings, return the minimum number of rooms required so that no two meetings in the same room overlap.

Constraints

• 0 ≤ meetings.length ≤ 10⁴
• 0 ≤ start < end ≤ 10⁶

Approach — Heaps / Top-K

This is a Heaps / Top-K problem. The idea: use a heap so the min, max, or top-k element stays reachable in O(log n) per operation. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n log k) time.

Solution code

Python

class Solution:
    def minMeetingRooms(self, meetings):
        import heapq
        meetings.sort()
        heap = []
        for s, e in meetings:
            if heap and heap[0] <= s:
                heapq.heappop(heap)
            heapq.heappush(heap, e)
        return len(heap)

Java

class Solution {
    public int minMeetingRooms(int[][] meetings) {
        if (meetings.length == 0) {
            return 0;
        }
        // Sort meetings by start time. Now scan left to right.
        Arrays.sort(meetings, (a, b) -> a[0] - b[0]);

        // Min-heap of end times — peek is the soonest-freeing room.
        PriorityQueue<Integer> endTimes = new PriorityQueue<>();
        for (int[] meeting : meetings) {
            // If the soonest-ending room is free, reuse it.
            if (!endTimes.isEmpty() && endTimes.peek() <= meeting[0]) {
                endTimes.poll();
            }
            endTimes.offer(meeting[1]);
        }
        // Heap size = number of overlapping meetings at the peak = rooms needed.
        return endTimes.size();
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.