<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:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        """
        So I think we should use heap to get the latest the meeting room.
        Because the due time is updating, and we don't want to sort the entire array at every iteration, which is very time consuming.

        """
        meetings.sort(key=lambda x:x[0])

        # heap stores (available time: room number: meeting count) pairs
        heap = [[0,i,0] for i in range(n)]
        heapq.heapify(heap)

        for start,end in meetings:
            duration = end-start
            # if there is no empty room currently
            if start<heap[0][0]:
                due,number,count = heapq.heappop(heap)
                # delay the start time, keep the duration
                due += duration
                count+=1
                heapq.heappush(heap,[due,number,count])

            # if there are one or more empty rooms
            else:
                # store [room number: available time:meeting count] pairs
                # because we want to sort based on room number than due time
                empty_room = []
                # we should pop all empty rooms
                while heap and start>=heap[0][0]:
                    due,number,count = heapq.heappop(heap)
                    # heapq.heappush(empty_room,[number,due,count])
                    empty_room.append([number,due,count])
                empty_room.sort(key=lambda x:(x[0],x[1]))
                number,due,count = empty_room.pop(0)
                # use the room with the lowest room number
                # number,due,count = heapq.heappop(empty_room)
                due = end
                count+=1
                heapq.heappush(heap,[due,number,count])
                # push other empty rooms back to the heap
                while empty_room:
                    # number,due,count = heapq.heappop(empty_room)
                    number,due,count = empty_room.pop()
                    heapq.heappush(heap,[due,number,count])
            
        heap.sort(key= lambda x:(-x[2],x[1]))
    
        return heap[0][1]


1172