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

class Solution {
public:
    struct Meeting {
        int64_t start;
        int64_t end;

        inline int duration() const {
            return end - start;
        }

        inline bool operator<(const Meeting& other) const {
            return start > other.start;
        }
    };

    struct Event {
        int64_t time;
        int room_id;
        int meeting_id;

        inline bool operator<(const Event& other) const {
            return time > other.time || (time == other.time && room_id > other.room_id);
        }
    };

    int mostBooked(int n, vector<vector<int>>& in_meetings) {
        std::vector<int> count(n, 0);
        std::vector<Meeting> meetings;
        meetings.reserve(in_meetings.size());
        for (int i = 0; i < in_meetings.size(); ++i) {
            const auto& in_meeting = in_meetings[i];
            meetings.push_back({in_meeting[0], in_meeting[1]});
        }

        std::sort(meetings.begin(), meetings.end(), [](const auto& a, const auto& b) {
            return a.start < b.start;
        });

        std::priority_queue<Meeting> delayed_meetings;

        std::priority_queue<Event> events;

        // The ongoing meeting in each room.
        std::priority_queue<int, std::vector<int>, std::greater<int>> avail_rooms;
        for (int i = 0; i < n; ++i) {
            avail_rooms.push(i);
        }

        for (int i = 0; i < meetings.size(); ++i) {
            const auto& meeting = meetings[i];

            while (!events.empty()) {
                const auto top = events.top();
                if (top.time <= meeting.start) {
                    events.pop();
                    avail_rooms.push(top.room_id);
                } else {
                    break;
                }
            }

            if (!avail_rooms.empty()) {
                const auto top = avail_rooms.top();
                std::cout << "Delayed meeting started at " << meeting.start << " in room " << top <<  std::endl;
                avail_rooms.pop();
                ++count[top];
                events.push({
                    meeting.start + meeting.duration(),
                    top,
                    i,
                });
            } else if (!events.empty()) {
                const auto top = events.top();
                events.pop();
                std::cout << "Delayed meeting started at " << top.time << "in room " << top.room_id << std::endl;
                ++count[top.room_id];
                events.push({
                    top.time + meeting.duration(),
                    top.room_id,
                    i
                });
            } else {
                std::cout << "WWW" << std::endl;
            }
        }

        int max_count = 0;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (count[i] > max_count) {
                max_count = count[i];
                ans = i;
            }
        }
        return ans;
    }
};
104256