Hello, fellow coders!
In this article, we will tackle a problem that involves scheduling meetings in the rooms. We are given a set of meetings represented by their start and end times. Our goal is to assign rooms to these meetings in an optimal manner and determine the room that holds the most meetings. We will explore an approach that considers room availability and start times to find the solution.
Link to the problem - 2402. Meeting Rooms III
Problem Description
Given an integer n representing the number of rooms and a 2D integer array meetings representing the start and end times of each meeting, we need to allocate rooms to the meetings according to the following rules:
Each meeting will be assigned to the lowest-numbered available room.
If no rooms are available, the meeting will be delayed until a room becomes free, while preserving its original duration.
When a room becomes available, meetings with earlier original start times should be given priority.
Our task is to find the room that holds the most meetings based on these rules. If multiple rooms have the same maximum number of meetings, we return the room with the lowest number.
Intuition
The intuition behind solving this problem is to keep track of the end time of each room and book the earliest available room with the lowest index in the list. We will use two arrays to store the counters of the meetings in each room and the earliest end time for each room.
Approach
Since JavaScript does not have a built-in Heap data structure, we can solve this problem using just an array and two loops. We will iterate through the meetings using the map
method, and for each meeting iteration, we will iterate through the rooms using a for
loop. This approach allows us to check all the rooms and find the room with the earliest end time.
Read the code and follow the walkthrough below to understand the solution better. It is recommended to create your own doodles and explain the solution to yourself for better comprehension.
Complexity
-
Time complexity: O(m * n) => O(n)
- Here, m represents the number of meetings, and n represents the number of rooms. The overall time complexity is linear.
- It's important to note that the Chrome web browser uses the Timsort implementation, which is a hybrid of merge sort and insertion sort. So, the time complexity of our
sort
method is O(n*logn). However, for small arrays, its time complexity is O(n).
-
Space complexity: O(n)
- The rooms counter array and available rooms array have the same length, which is n.
- Additionally, we introduce two integer variables and one boolean variable, resulting in a total of three variables with constant space complexity.
- Therefore, the overall space complexity is O(2 * n) + O(1 * 3).
Walkthrough
First, we define two arrays:
rooms_meetings_counter
andavailable_rooms
. Therooms_meetings_counter
array will keep the counters of the meetings in each room, and theavailable_rooms
array will store the earliest end time for each room. The indexes in these arrays represent the room number. Take your time to understand this step as it is crucial to the logic.We sort the meetings array by their start time using the
sort
method. This sorting step is essential for our solution.Next, we iterate through the meetings using the
map
method. Alternatively, we can use afor
loop, but in my opinion, themap
method provides a more elegant solution.For each meeting iteration, we introduce two variables:
earliestRoomIdx
andearliestEndTime
. We start with the index 0 because we want to check all the rooms and find the room with the earliest end time. For the earliest end time, we initialize it with the maximum possible value, which can be eitherInfinity
orNumber.MAX_SAFE_INTEGER
.Within each meeting iteration, we iterate through all the rooms we have.
The first
if
condition checks the availability of the room by comparing the start time with the end time of all the rooms stored in theavailable_rooms
array. By default, theavailable_rooms
array is populated with -1 since the start time cannot be a negative value. The condition checks if the current room is available for the current meeting. If it is, we update theavailable_rooms
array with the end time of the current meeting and break out of thefor
loop.The second
if
condition is responsible for tracking the earliest end time and the corresponding room index. If we do not find an available room in the previous step, we check if the end time of the current room iteration is less than the registered earliest end time. If it is, we update the earliest end time and the earliest room index with the index of the current room iteration.The last
if
condition checks if all the rooms are busy. If this condition is true, it means that no rooms are available for the current meeting. In this case, we assign the current meeting to the room with the earliest end time. To do this, we use the earliest room index and update this room with a new end time, which is equal to the previous end time plus the duration of the current meeting.Now, let's discuss the purpose of the boolean flag
isAvailableRoomExist
. When we break out of thefor
loop and find a free room, we should not trigger the lastif
condition from step 8. This condition should only be triggered when there is no available room for the meeting. The boolean variableisAvailableRoomExist
indicates that we did not find a room, but we found the earliest room index.In the last step, we find the maximum value in the
rooms_meetings_counter
array and retrieve its index using theindexOf
function. This will return the lowest index with the maximum value.Congratulations! You have solved the problem.
Reward yourself with a cup of coffee.
You deserve it! π
Example
Let's use the data from the test case to see how the code works.
We have the input: [[1,20],[2,10],[3,5],[4,9],[6,8]]
.
The first three meetings will take all three available rooms, resulting in the following arrays:
rooms_meetings_counter = [1, 1, 1]
available_rooms = [20, 10, 5]
This means that we have reached the first if
condition, and the rest of the code is skipped.
The last two meetings are different:
- We skip the first
if
condition. - We iterate through the rooms to find the earliest end time and the earliest room index in the second
if
condition. - We update the counter value for the current room.
For the meeting [4,9], the earliest end time is at index 2, and the earliest end time is 5. So, in the last if
condition, we pick available_rooms[2]
and assign the value of 5 + (9-4). As a result, we have the following arrays:
rooms_meetings_counter = [1, 1, 2]
available_rooms = [20, 10, 10]
The last meeting is [6, 8]. We iterate from room 0 up to room 2, and it seems that the earliest end time here is 10 at index 1. If we check the last room,
10 < 10 is false, and we do not update the earliest room index further.
As a result, we have the following arrays:
rooms_meetings_counter = [1, 2, 2]
available_rooms = [20, 12, 10]
Now, we can proceed to step 10 and return the index 1 as our result.
Implementation
/**
* @param {number} n
* @param {number[][]} meetings
* @return {number}
*/
var mostBooked = function(n, meetings) {
let rooms_meetings_counter = new Array(n).fill(0);
let available_rooms = new Array(n).fill(-1);
meetings.sort((a, b) => a[0] - b[0]);
meetings.map((meeting) => {
let [start, end] = meeting;
let earliestRoomIdx = 0;
let earliestEndTime = Number.MAX_SAFE_INTEGER;
let isAvailableRoomExist = false;
for (let i = 0; i < n; i++) {
if (available_rooms[i] <= start) {
rooms_meetings_counter[i]++;
available_rooms[i] = end;
isAvailableRoomExist = true;
break;
}
if (available_rooms[i] < earliestEndTime) {
earliestEndTime = available_rooms[i];
earliestRoomIdx = i;
}
}
if (!isAvailableRoomExist) {
rooms_meetings_counter[earliestRoomIdx]++;
available_rooms[earliestRoomIdx] += end - start;
}
});
return rooms_meetings_counter.indexOf(Math.max(...rooms_meetings_counter));
};
Conclusion
Great job on finishing the article! I hope the solution explanation was helpful and easy to follow. Remember, these leetcode tasks can be tough, but with practice and a positive attitude, you'll do just great. Keep coding, keep learning, and best of luck on your future coding adventures.
Happy coding and take care!
Top comments (1)
good job! Keep doing...