Meeting Rooms III

I think this question is rather straightforward.

Since we need to allocate meetings to rooms, we need to track which rooms are viable at the meeting start time. However, sometimes there are not any rooms available at the meeting start time, meaning we also need to track what room frees up next.

To do this, we have two minimum heaps:

• one to track the viableRooms
  • this contains all the viable room numbers as integers
• another to track the takenRooms
  • sorts from when the room frees up and the room numbers stored inside of pair<long long, int> respectively
  • note, long long is used since it is possible to have integer overflow if all meetings are scheduled into one room

Then, we can just iterate through all the meetings.

For each meeting, first we check if there are any takenRooms that free up before the meeting start time, and can add them back into the pool of viableRooms. However, if there are not any viableRooms that exist, then we just take the takenRoom that frees up the earliest and use that as the meeting start time instead.

Finally, we just simply take the element of viableRooms with the smallest index, add the meeting duration to the respective meeting start time and add it into the takenRooms priority queue. We make sure to also increment the freq of the respective room that we scheduled a meeting in, before repeating it for all the meetings.

Now, we can simply just iterate through all the rooms and return the lowest index meeting room that held the most meetings.

code

class Solution {
public:
    int mostBooked(int n, vector<vector<int>>& meetings) {
        sort(meetings.begin(), meetings.end());

        priority_queue<int, vector<int>, greater<int>> viableRooms;
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> takenRooms;

        vector<int> freq(n, 0);

        for (int i = 0; i < n; ++i) {
            viableRooms.push(i);
        }

        for (vector<int>& meeting : meetings) {
            long long meetingStartTime = meeting[0];
            while(!takenRooms.empty()) {
                if (takenRooms.top().first <= meetingStartTime) {
                    viableRooms.push(takenRooms.top().second);
                    takenRooms.pop();
                } else if (viableRooms.empty()) {
                    meetingStartTime = takenRooms.top().first;
                    viableRooms.push(takenRooms.top().second);
                    takenRooms.pop();
                    break;
                } else {
                    break;
                }
            }

            int roomNumber = viableRooms.top();
            viableRooms.pop();

            takenRooms.emplace(meetingStartTime + meeting[1] - meeting[0], roomNumber);
            ++freq[roomNumber];
        }

        int ansIndex = 0;
        int maxFreq = freq[0];
        for (int i = 1; i < freq.size(); ++i) {
            if (freq[i] > maxFreq) {
                maxFreq = freq[i];
                ansIndex = i;
            }
        }
        return ansIndex;
    }
};

complexity

• Time: O(m log(m) + m log(n)) where n is the same as n and m is the number of elements inside of meetings
• Space: O(n)

learnings

• apparently the sort implementation inside STL for c++ uses introsort which consists of 3 sorting algorithms:
  • quicksort (default)
  • heapsort (if it exceeds the maximum depth limit, to try avoid quicksort's worst case scenario of O(n^2))
  • insertion sort (optimal for small arrays and partially sorted ones)
• time complexity: Best, Average and worst of O(n log(n))
• space complexity: uses O(log(n)) auxiliary stack space

time taken

• 28 minutes and 17 seconds