Meetings room III - Elegant solution in JavaScript with detailed explanation

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

1. First, we define two arrays: rooms_meetings_counter and available_rooms. The rooms_meetings_counter array will keep the counters of the meetings in each room, and the available_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.

2. We sort the meetings array by their start time using the sort method. This sorting step is essential for our solution.

3. Next, we iterate through the meetings using the map method. Alternatively, we can use a for loop, but in my opinion, the map method provides a more elegant solution.

4. For each meeting iteration, we introduce two variables: earliestRoomIdx and earliestEndTime. 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 either Infinity or Number.MAX_SAFE_INTEGER.

5. Within each meeting iteration, we iterate through all the rooms we have.

6. 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 the available_rooms array. By default, the available_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 the available_rooms array with the end time of the current meeting and break out of the for loop.

7. 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.

8. 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.

9. Now, let's discuss the purpose of the boolean flag isAvailableRoomExist. When we break out of the for loop and find a free room, we should not trigger the last if condition from step 8. This condition should only be triggered when there is no available room for the meeting. The boolean variable isAvailableRoomExist indicates that we did not find a room, but we found the earliest room index.

10. In the last step, we find the maximum value in the rooms_meetings_counter array and retrieve its index using the indexOf function. This will return the lowest index with the maximum value.

11. 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:

1. We skip the first if condition.
2. We iterate through the rooms to find the earliest end time and the earliest room index in the second if condition.
3. 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!

Comments

[Timoschenko Viacheslau]

good job! Keep doing...