Scale Engineer

Meeting Rooms III

Hard
#2186Time: O(M log M + M * N), where M is the number of meetings and N is the number of rooms. Sorting takes O(M log M). The main loop iterates M times, and inside it, we may perform a linear scan of N rooms, resulting in O(M * N).Space: O(N) to store the availability time and meeting counts for each room.2 companies
Algorithms
Sorting
Data structures
ArrayHash TableHeap (Priority Queue)
Companies
PayPalPinterest

Prompt

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:

  1. Each meeting will take place in the unused room with the lowest number.
  2. 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.
  3. 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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach simulates the meeting allocation process by iterating through meetings sorted by start time. For each meeting, it performs a linear scan through the rooms to find an available one or the one that frees up earliest. This is straightforward but less efficient for a large number of rooms.

Algorithm

  • Sort the meetings array by start time.
  • Initialize roomAvailabilityTime array of size n with zeros to track when each room becomes free.
  • Initialize meetingCounts array of size n with zeros.
  • Iterate through each sorted meeting [start, end]:
    • Linearly scan rooms 0 to n-1 to find the first available room i (where roomAvailabilityTime[i] <= start).
    • If an available room i is found, assign the meeting to it. Update roomAvailabilityTime[i] = end and increment meetingCounts[i].
    • If no room is available, find the room j that will be free the earliest by finding the minimum roomAvailabilityTime. Assign the delayed meeting to room j. The new end time will be roomAvailabilityTime[j] + (end - start). Update roomAvailabilityTime[j] and increment meetingCounts[j].
  • After iterating through all meetings, find the room index with the maximum count in meetingCounts. Handle ties by choosing the smaller index.

Walkthrough

In this method, we directly simulate the process described in the problem. We maintain an array, roomAvailabilityTime, of size n, where each element stores the time when the corresponding room will become free. Another array, meetingCounts, of the same size, keeps track of how many meetings each room has hosted.

First, we must sort the meetings array by their start times. This ensures we process meetings in chronological order, which is a key requirement for correctly handling priorities for delayed meetings.

We then iterate through each sorted meeting [start, end]. For each meeting, we attempt to find an available room. We do this by scanning through our roomAvailabilityTime array from index 0 to n-1. The first room i for which roomAvailabilityTime[i] <= start is the one we select, as it satisfies both being available and having the lowest index.

If such a room is found, we schedule the meeting in it. This involves updating roomAvailabilityTime[i] to the meeting's end time and incrementing meetingCounts[i].

If, after checking all rooms, none are available at the meeting's start time, the meeting must be delayed. It has to wait for the first room to become free. To find this room, we perform another linear scan over roomAvailabilityTime to find the room j with the minimum availability time. This meeting will start at roomAvailabilityTime[j]. The duration of the meeting remains end - start. Therefore, the new end time for this meeting in room j will be roomAvailabilityTime[j] + (end - start). We update roomAvailabilityTime[j] to this new value and increment meetingCounts[j].

After processing all meetings, we iterate through the meetingCounts array to find the room index that has the highest count. In case of a tie, the problem specifies to return the room with the lower index, which we can handle during our search for the maximum.

import java.util.Arrays; class Solution {    public int mostBooked(int n, int[][] meetings) {        Arrays.sort(meetings, (a, b) -> Integer.compare(a[0], b[0]));         long[] roomAvailabilityTime = new long[n];        int[] meetingCounts = new int[n];         for (int[] meeting : meetings) {            int start = meeting[0];            int end = meeting[1];            boolean roomFound = false;            int earliestFreeRoom = 0;            long earliestFreeTime = Long.MAX_VALUE;             // Find an available room with the lowest index            for (int i = 0; i < n; i++) {                if (roomAvailabilityTime[i] <= start) {                    roomAvailabilityTime[i] = end;                    meetingCounts[i]++;                    roomFound = true;                    break;                }                if (roomAvailabilityTime[i] < earliestFreeTime) {                    earliestFreeTime = roomAvailabilityTime[i];                    earliestFreeRoom = i;                }            }             // If no room was available, use the one that becomes free earliest            if (!roomFound) {                roomAvailabilityTime[earliestFreeRoom] += (end - start);                meetingCounts[earliestFreeRoom]++;            }        }         int maxMeetings = -1;        int resultRoom = -1;        for (int i = 0; i < n; i++) {            if (meetingCounts[i] > maxMeetings) {                maxMeetings = meetingCounts[i];                resultRoom = i;            }        }        return resultRoom;    }}

Complexity

Time

O(M log M + M * N), where M is the number of meetings and N is the number of rooms. Sorting takes O(M log M). The main loop iterates M times, and inside it, we may perform a linear scan of N rooms, resulting in O(M * N).

Space

O(N) to store the availability time and meeting counts for each room.

Trade-offs

Pros

  • Simple logic, easy to understand and implement.

  • Low memory overhead, uses basic arrays.

Cons

  • Inefficient time complexity O(M*N), which can be slow if M and N are large.

Solutions

class Solution {public  int mostBooked(int n, int[][] meetings) {    Arrays.sort(meetings, (a, b)->a[0] - b[0]);    PriorityQueue<int[]> busy =        new PriorityQueue<>((a, b)->a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);    PriorityQueue<Integer> idle = new PriorityQueue<>();    for (int i = 0; i < n; ++i) {      idle.offer(i);    }    int[] cnt = new int[n];    for (var v : meetings) {      int s = v[0], e = v[1];      while (!busy.isEmpty() && busy.peek()[0] <= s) {        idle.offer(busy.poll()[1]);      }      int i = 0;      if (!idle.isEmpty()) {        i = idle.poll();        busy.offer(new int[]{e, i});      } else {        var x = busy.poll();        i = x[1];        busy.offer(new int[]{x[0] + e - s, i});      }      ++cnt[i];    }    int ans = 0;    for (int i = 0; i < n; ++i) {      if (cnt[ans] < cnt[i]) {        ans = i;      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem