Meeting Rooms III

HardHeapheap

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

There are n rooms numbered 0 to n - 1. Each meetings[i] = [start, end] is a meeting that wants the half-open time range [start, end). All start times are distinct. Meetings are handled in order of start time with these rules: 1. A meeting takes the free room with the **lowest number**. 2. If no room is free, the meeting waits until a room frees up and keeps its original duration. If several rooms free up at the same time, it takes the lowest-numbered one. 3. When a room frees up, delayed meetings get it before later meetings, in order of their original start time. Return the number of the room that hosted the most meetings. If several rooms tie, return the lowest number.

Examples

Input: n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
Output: 0
[0,10) takes room 0 and [1,5) takes room 1. [2,7) waits for room 1 and runs [5,10). [3,4) waits until 10, when both rooms free up, so it takes room 0. Each room hosts 2 meetings, so the answer is 0.
Input: n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
Output: 1
Rooms 0, 1 and 2 start meetings at 1, 2 and 3. [4,9) waits for room 2 (free at 5) and runs [5,10). [6,8) waits until 10, when rooms 1 and 2 both free up, so it takes room 1 and runs [10,12). Rooms 1 and 2 host 2 meetings each, so the answer is 1.

Constraints

  • 1 <= n <= 100
  • 1 <= meetings.length <= 10^5
  • 0 <= start < end <= 5 * 10^5
  • All `start` values are distinct.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More heap problems