<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:
        # Sort by start time to simplify computation
        meetings.sort()
        print(meetings)
        timeStamp = 0

        # Delay so far
        delay = 0

        """
        When all rooms are booked I am going go to into the room that finishes the earliest.

        But it is also possible that multiple rooms finish the earliest. Because of point #1 I need to break ties for this.
        """

        count = [0 for _ in range(n)]

        # What is available? Everything (every room) by default.
        available = [i for i in range(n)]
        heapq.heapify(available)

        # What are the ongoing meetings and when are they ending?
        # When is the earliest end time so far? I need a heap for that.
        # I will store the endTime, and the roomNumber

        # This will hold all ongoing meetings, i.e. meetings that have not finished yet
        ending = []

        # Go through each meeting
        for i in range(len(meetings)):
            # print("start", available, ending)
            start = meetings[i][0] 
            end = meetings[i][1] 

            # if there are ongoing meetings that have ended already, then free up those rooms
            while ending and ending[0][0] <= start:
                timeStamp, freeRoom = heapq.heappop(ending)
                heapq.heappush(available, freeRoom)

            if available:
                # Get the first available meeting and go into it
                
                # But consider the delay
                delta = 0 if start >= timeStamp else (timeStamp - start)
                # start is gonna be the max of the thing im going to add and the end time of the last thing
                availableRoom = heapq.heappop(available)
                heapq.heappush(ending, (end + delta, availableRoom))
                count[availableRoom] += 1
              
            else:
                # Nothing is available right now. I will go into the room with the closest end time soon/
                # Delay needed (because of overlap)
                nextEnding = ending[0][0]
                timeStamp = nextEnding

                if (start <= nextEnding):
                    # "Wait for meetings to finish"
                    delta = nextEnding - start

                    while ending and ending[0][0] == nextEnding:
                        timeStamp, freeRoom = heapq.heappop(ending)
                        heapq.heappush(available, freeRoom)

                    availableRoom = heapq.heappop(available)
                    heapq.heappush(ending, (end + delta, availableRoom))
                    count[availableRoom] += 1
                    
                # Delay not needed
                else:
                    availableRoom = heapq.heappop(ending)[1]
                    heapq.heappush(available, availableRoom)
                    while ending and ending[0][0] <= start:
                        availableRoom = heapq.heappop(ending)[1]
                        heapq.heappush(available, availableRoom)
                    
                    heapq.heappush(ending, (end, availableRoom))
                    count[availableRoom] += 1

            # print("end", available, ending)
            
        final = 0
        cmax = 0
        for i in range(n-1,-1,-1):
            if count[i] >= cmax:
                final = i
                cmax = count[i]

        # print(count)
        return final






        
1271