<p>You are given an integer <code>n</code>. There are <code>n</code> rooms numbered from <code>0</code> to <code>n - 1</code>.</p>

<p>You are given a 2D integer array <code>meetings</code> where <code>meetings[i] = [start<sub>i</sub>, end<sub>i</sub>]</code> means that a meeting will be held during the <strong>half-closed</strong> time interval <code>[start<sub>i</sub>, end<sub>i</sub>)</code>. All the values of <code>start<sub>i</sub></code> are <strong>unique</strong>.</p>

<p>Meetings are allocated to rooms in the following manner:</p>

<ol>
	<li>Each meeting will take place in the unused room with the <strong>lowest</strong> number.</li>
	<li>If there are no available rooms, the meeting will be delayed until a room becomes free. The delayed meeting should have the <strong>same</strong> duration as the original meeting.</li>
	<li>When a room becomes unused, meetings that have an earlier original <strong>start</strong> time should be given the room.</li>
</ol>

<p>Return<em> the <strong>number</strong> of the room that held the most meetings. </em>If there are multiple rooms, return<em> the room with the <strong>lowest</strong> number.</em></p>

<p>A <strong>half-closed interval</strong> <code>[a, b)</code> is the interval between <code>a</code> and <code>b</code> <strong>including</strong> <code>a</code> and <strong>not including</strong> <code>b</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
<strong>Output:</strong> 0
<strong>Explanation:</strong>
- 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. 
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
<strong>Output:</strong> 1
<strong>Explanation:</strong>
- 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. 
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 100</code></li>
	<li><code>1 &lt;= meetings.length &lt;= 10<sup>5</sup></code></li>
	<li><code>meetings[i].length == 2</code></li>
	<li><code>0 &lt;= start<sub>i</sub> &lt; end<sub>i</sub> &lt;= 5 * 10<sup>5</sup></code></li>
	<li>All the values of <code>start<sub>i</sub></code> are <strong>unique</strong>.</li>
</ul>

#include <queue>

struct MeetingRoom {
    long int room_num;
    long int available_time;
};

struct Meeting {
    long int start_time;
    long int end_time;
};

class Solution {
public:
    int mostBooked(int n, vector<vector<int>>& meeting_vects) {
        const auto compare_rooms = [&n](const MeetingRoom& a, const MeetingRoom& b) {
            return a.available_time > b.available_time;
        };
        const auto compare_available_rooms = [](const MeetingRoom& a, const MeetingRoom& b) {
            return a.room_num > b.room_num;
        };
        // Keeps track of the time when room will be free.
        std::priority_queue<MeetingRoom, std::deque<MeetingRoom>, decltype(compare_rooms)>
            room_availability(compare_rooms);
        // Because the priority queue doesn't know when it now, it can't prioritize
        // between all available by room number, so we will put these in a separate queue
        // that prioritizes by room number.
        std::priority_queue<MeetingRoom, std::deque<MeetingRoom>,
                            decltype(compare_available_rooms)> 
            available_now(compare_available_rooms);
        // Counts the number of meetings assigned to a meeting room (for final output).
        std::unordered_map<int, int> meeting_count;
        // We start with all rooms available and zero counts.
        for (int i = 0; i < n; ++i) {
            available_now.push(MeetingRoom{i, 0});
            meeting_count[i] = 0;
        }
        // Reverse sort the meetings by start time so we can pop from the end. This order
        // never changes, as the original start time determines order, and we know there are
        // no ties, as original start times are unique.
        const auto compare_meetings = [](const Meeting& m1, 
                                         const Meeting& m2) {
            return m1.start_time > m2.start_time;
        };
        std::vector<Meeting> meetings;
        meetings.reserve(meeting_vects.size());
        for (const auto meeting_vect : meeting_vects) {
            meetings.push_back(Meeting({meeting_vect[0], meeting_vect[1]}));
        }
        sort(meetings.begin(), meetings.end(), compare_meetings);
        printf("number of meetings: %d\n", meetings.size());
    
        long int time = 0;
        int countdown = 100000;//meetings.size();
        while (!meetings.empty()) {
            //printf("num meetings: %d, time %d\n", meetings.size(), time);
            Meeting& next_meeting = meetings[meetings.size()-1];
            //printf("next meeting: [%d, %d)\n", next_meeting.start_time, next_meeting.end_time);
            // We can't do anything useful until there is a meeting room free.
            if (available_now.empty() && 
                room_availability.top().available_time > time) {
                time = room_availability.top().available_time;
            }
            // If the next meeting doesn't start yet, advance the time to the next meeting
            // start time.
            if (next_meeting.start_time > time) {
                time = next_meeting.start_time;
            }
            // If the next meeting was supposed to start before now, we need to delay it so
            // we know when it will actually end.
            else if (next_meeting.start_time < time) {
                //printf("delaying [%d, %d) until [%d, %d)\n", next_meeting.start_time, next_meeting.end_time, time, next_meeting.end_time + (time - next_meeting.start_time));
                next_meeting.end_time += (time - next_meeting.start_time); 
                next_meeting.start_time = time;
            }
            // First shift any newly available rooms to the available_now queue.
            while (!room_availability.empty() && 
                    room_availability.top().available_time <= time) {
                const auto available_room = room_availability.top();
                room_availability.pop();
                //printf("room %d available now.\n", available_room.room_num);
                available_now.push(available_room);
            }
            // If there are rooms available now, get the lowest-numbered one.
            if (!available_now.empty()) {
                auto room = available_now.top();
                available_now.pop();
                // Now the room will be available at the end of this meeting
                //printf("assigning meeting [%d, %d) to room %d\n", next_meeting.start_time, next_meeting.end_time, room.room_num);
                room.available_time = next_meeting.end_time;
                room_availability.push(room);
                meeting_count[room.room_num]++;
                meetings.pop_back();
            }
            else {
                // Delay the meeting until the next available time.
                const int soonest_available_time = room_availability.top().available_time;
                //printf("delaying by %d\n", (soonest_available_time - next_meeting.start_time));
                next_meeting.end_time += (soonest_available_time - next_meeting.start_time);
                next_meeting.start_time = soonest_available_time;
            }
            countdown--;
            //if (countdown == 0) break;
        }
        printf("num meetings at end: %d\n", meetings.size());
        // Now find the room with the largest count. 
        int max_room_num = -1, max_count = -1;
        for (int room_num = 0; room_num < n; ++room_num) {
            if (meeting_count[room_num] > max_count) {
                max_count = meeting_count[room_num];
                max_room_num = room_num;
            }
        }
        return max_room_num;
    }
};
118831