← Back to Heap Pattern

📚 Meeting Rooms III – Java Cheat Sheet

📌 What Is It?

The problem involves scheduling meetings in a set of meeting rooms such that the number of meetings held in each room is minimized. If a meeting room is free, it can be reused for another meeting. If multiple rooms are free, the room with the smallest index is chosen.

To solve this efficiently, we use two heaps:

• Min-Heap 1: Tracks the end times of meetings currently scheduled in rooms.
• Min-Heap 2: Tracks the available room indices.

🧱 Pattern Template

class Solution {
    public int mostBooked(int n, int[][] meetings) {
        // Step 1: Sort meetings by start time
        Arrays.sort(meetings, (a, b) -> a[0] - b[0]);

        // Step 2: Initialize heaps
        PriorityQueue<Integer> availableRooms = new PriorityQueue<>(); // Room indices
        PriorityQueue<int[]> ongoingMeetings = new PriorityQueue<>((a, b) -> a[0] - b[0]); // [endTime, roomIndex]
        int[] roomUsage = new int[n]; // Tracks the number of meetings held in each room

        // Add all rooms to the availableRooms heap
        for (int i = 0; i < n; i++) {
            availableRooms.offer(i);
        }

        // Step 3: Process each meeting
        for (int[] meeting : meetings) {
            int start = meeting[0];
            int end = meeting[1];

            // Free up rooms that have completed their meetings
            while (!ongoingMeetings.isEmpty() && ongoingMeetings.peek()[0] <= start) {
                availableRooms.offer(ongoingMeetings.poll()[1]);
            }

            // If no rooms are available, delay the meeting in the earliest finishing room
            if (availableRooms.isEmpty()) {
                int[] earliest = ongoingMeetings.poll();
                int delayedRoom = earliest[1];
                int newEnd = earliest[0] + (end - start);
                ongoingMeetings.offer(new int[]{newEnd, delayedRoom});
                roomUsage[delayedRoom]++;
            } else {
                // Assign the meeting to the smallest available room
                int room = availableRooms.poll();
                ongoingMeetings.offer(new int[]{end, room});
                roomUsage[room]++;
            }
        }

        // Step 4: Find the room with the maximum usage
        int maxUsage = 0, resultRoom = 0;
        for (int i = 0; i < n; i++) {
            if (roomUsage[i] > maxUsage) {
                maxUsage = roomUsage[i];
                resultRoom = i;
            }
        }

        return resultRoom;
    }
}

📊 Time Complexity

• Sorting Meetings: O(m log m) – Sorting the meetings by start time, where m is the number of meetings.
• Heap Operations: O(m log n) – Adding and removing elements from heaps for m meetings and n rooms.
• Overall Complexity: O(m log m + m log n).

✅ Use Cases

• Scheduling meetings in limited rooms
• Finding the most used room in a meeting schedule
• Applications in resource allocation and scheduling

📘 Common LeetCode Problems

• 2402. Meeting Rooms III [Medium] Heap

🧪 Example: Meeting Rooms III

Input: n = 2, meetings = [[0, 10], [1, 5], [2, 7], [3, 4]]
Output: 0

Explanation:
- Room 0: [0, 10]
- Room 1: [1, 5], [5, 7]
- Room 0 is used the most (1 meeting).

▶️ View Animation

💡 Pro Tips

• Sort meetings by start time to process them in chronological order.
• Use two heaps to efficiently track available rooms and ongoing meetings.
• Edge cases: overlapping meetings, no available rooms, large input sizes.