2402. Meeting Rooms III

Meeting Rooms III (LeetCode 2402) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Heap (Priority Queue) Patterns pattern, in the Scheduling / Minimum Cost (Greedy with Priority Queue) subpattern.

• NeetCode 250 · #226 of 250 · Intervals

How to solve Meeting Rooms III

Meeting Rooms III is a Scheduling and Minimum Cost problem, part of Heap (Priority Queue) Patterns. Solve scheduling and optimization problems using priority queue with greedy approach.

Work towards the solution in these steps:

1. Sort meetings based on start times.
2. Use two min heaps, the first one keeps track of the numbers of all the rooms that are free. The second heap keeps track of the end times of all the meetings that are happening and the room that they are in.
3. Keep track of the number of times each room is used in an array.

The reference solution runs in O(mlogm + n + mlogn) time and O(n) space.

The Meeting Rooms III solution and editorial walks through the full approach with reference code.

Problem statement

You are given an integer n. There are n rooms numbered from 0 to n - 1.

You are given a 2D integer array meetings where meetings[i] = [starti, endi] means that a meeting will be held during the half-closed time interval [starti, endi). All the values of starti are unique.

Meetings are allocated to rooms in the following manner:

- Each meeting will take place in the unused room with the lowest number.

- If there are no available rooms, the meeting will be delayed until a room becomes free. The delayed meeting should have the same duration as the original meeting.

- When a room becomes unused, meetings that have an earlier original start time should be given the room.

Return the number of the room that held the most meetings. If there are multiple rooms, return the room with the lowest number.

A half-closed interval [a, b) is the interval between a and b including a and not including b.

Example 1:

Input: n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]] Output: 0 Explanation: - At time 0, both rooms are not being used. The first meeting starts in room 0. - At time 1, only room 1 is not being used. The second meeting starts in room 1. - At time 2, both rooms are being used. The third meeting is delayed. - At time 3, both rooms are being used. The fourth meeting is delayed. - At time 5, the meeting in room 1 finishes. The third meeting starts in room 1 for the time period [5,10). - At time 10, the meetings in both rooms finish. The fourth meeting starts in room 0 for the time period [10,11). Both rooms 0 and 1 held 2 meetings, so we return 0.

Example 2:

Input: n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]] Output: 1 Explanation: - At time 1, all three rooms are not being used. The first meeting starts in room 0. - At time 2, rooms 1 and 2 are not being used. The second meeting starts in room 1. - At time 3, only room 2 is not being used. The third meeting starts in room 2. - At time 4, all three rooms are being used. The fourth meeting is delayed. - At time 5, the meeting in room 2 finishes. The fourth meeting starts in room 2 for the time period [5,10). - At time 6, all three rooms are being used. The fifth meeting is delayed. - At time 10, the meetings in rooms 1 and 2 finish. The fifth meeting starts in room 1 for the time period [10,12). Room 0 held 1 meeting while rooms 1 and 2 each held 2 meetings, so we return 1.

Constraints:

- 1 <= n <= 100

- 1 <= meetings.length <= 105

- meetings[i].length == 2

- 0 <= starti < endi <= 5 105

- All the values of starti are unique.

Topics and companies

Topics: Array, Hash Table, Sorting, Heap (Priority Queue), Simulation.

How to practise Meeting Rooms III on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(mlogm + n + mlogn) time and O(n) space.

Open Meeting Rooms III in the code editor, or read the Meeting Rooms III editorial for a worked solution with its approach and complexity analysis.

Where Meeting Rooms III sits in the DSA pattern sheet

• Heap (Priority Queue) Patterns pattern guide
• Scheduling / Minimum Cost (Greedy with Priority Queue) subpattern
• The full DSA patterns sheet

Problems related to Meeting Rooms III

Other problems that use the same Scheduling / Minimum Cost (Greedy with Priority Queue) and Heap (Priority Queue) Patterns techniques:

• Furthest Building You Can Reach — Medium, same subpattern
• IPO — Hard, same subpattern
• Longest Happy String — Medium, same subpattern
• Maximum Average Pass Ratio — Medium, same subpattern
• Meeting Rooms II — Medium, same subpattern
• Minimum Cost to Hire K Workers — Hard, same subpattern

Meeting Rooms III FAQ