Practice/Meta/Leetcode 2402. Meeting Rooms III

Leetcode 2402. Meeting Rooms III

CodingMust

Problem

You are managing a conference center with n identical rooms numbered from 0 to n - 1. You receive a list of meetings, where each meeting is represented as [start, end] indicating the meeting's start and end times.

Your task is to schedule all meetings according to these rules:

1. When a meeting starts, assign it to the lowest-numbered available room
2. If no room is available at the meeting's start time, the meeting must wait until a room becomes free
3. When a meeting is delayed, it maintains its original duration but starts as soon as any room becomes available
4. If multiple rooms become available simultaneously, choose the lowest-numbered room
5. If multiple delayed meetings are waiting when a room frees up, prioritize the meeting with the earliest original start time

Return the number (index) of the room that hosted the most meetings. If there's a tie, return the room with the lowest number.

Requirements

1. Implement an efficient room scheduling algorithm
2. Track which room hosts each meeting
3. Handle delayed meetings correctly, preserving their duration
4. Count meetings per room and identify the room with maximum usage
5. Break ties by selecting the lowest room number

Constraints

• 1 ≤ n ≤ 100
• 1 ≤ meetings.length ≤ 10^5
• meetings[i].length == 2
• 0 ≤ start_i < end_i ≤ 5 × 10^5
• All start times are unique
• Time complexity should be O(m log m + m log n) where m is the number of meetings
• Space complexity should be O(n + m)

Examples

Example 1:

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

• Meeting [0,10] → Room 0 (0 to 10)
• Meeting [1,5] → Room 1 (1 to 6)
• Meeting [2,7] → Room 1 is free at time 6, so it starts at 6 with duration 5, ending at 11
• Meeting [3,4] → Room 0 is free at time 10, so it starts at 10 with duration 1, ending at 11 Room 0: 2 meetings, Room 1: 2 meetings → Return 0 (lowest number) `

Example 2:

` Input: n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]] Output: 1 Explanation:

• Meeting [1,20] → Room 0 (1 to 20)
• Meeting [2,10] → Room 1 (2 to 12)
• Meeting [3,5] → Room 2 (3 to 8)
• Meeting [4,9] → Room 2 is free at 8, starts at 8 with duration 5, ends at 13
• Meeting [6,8] → Room 1 is free at 12, starts at 12 with duration 2, ends at 14 Room 0: 1 meeting, Room 1: 2 meetings, Room 2: 2 meetings → Return 1 (lowest among max) `