<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:
        timer = 0
        meeting_count = [0 for i in range(n)]       #[room 0: 1 meeting, room 1: 2 meetings]
        rooms_available = [(0,i) for i in range(n)] # need earliest number room to be available (will have to be a heap)  
        meetings.sort()
        curr_meeting = 0
        most_meetings = 0
        most_meetings_room = 0

        while curr_meeting < len(meetings):
            if timer >= meetings[curr_meeting][0]:                       # do we have a meeting that needs a room
            
                if timer >= rooms_available[0][0]:                      # do we have a room available
                    while timer > rooms_available[0][0]:                # clear the rooms so we know the lowest number one gets filled
                        _,room_num = heapq.heappop(rooms_available)
                        heapq.heappush(rooms_available,(timer,room_num))

                    while curr_meeting<len(meetings) and timer >= meetings[curr_meeting][0] and timer >= rooms_available[0][0]:              # do we have a meeting that needs a room
                        start_time,end_time = meetings[curr_meeting]
                        new_end_time = timer+(end_time-start_time)

                        _,room_num = heapq.heappop(rooms_available)
                        heapq.heappush(rooms_available,(new_end_time,room_num))
                        meeting_count[room_num]+=1
                        curr_meeting+=1

                        if meeting_count[room_num] > most_meetings:
                            most_meetings = meeting_count[room_num]
                            most_meetings_room = room_num
                        elif meeting_count[room_num] == most_meetings:
                            most_meetings_room = min(room_num,most_meetings_room)

            #timer+=1
            if curr_meeting < len(meetings):
                timer = max(meetings[curr_meeting][0],rooms_available[0][0])
                

        return most_meetings_room


'''
given n (number of rooms) -> labelled 0 to n-1
Meetings held from start up to but not including end
Start times are unique

Meetings get assigned to unused room of lowest number
No rooms available... have to wait until one becomes free

WHEN A ROOM BECOMES UNUSED, MEETINGS THAT HAVE AN EARLIER ORIGINAL START TIME SHOULD BE GIVEN THE ROOM {Queue}

Return the number of the room that held the most meetings (if more than one return the room with the lowest number)

n=2; meetings = [0,10],[1,5],[2,7],[3,4]

room 0, room 1
[0,10]           timer = 0  room0_count=1; room1_count=0
[1,10]  [1,5]    timer = 1  room0_count=1; room1_count=1
[2,10]  [2,5]    timer = 2  room0_count=1; room1_count=1 
[3,10]  [3,5]    timer = 3  room0_count=1; room1_count=1
[4,10]  [4,5]    timer = 4  room0_count=1; room1_count=1
[5,10]  [5,5+(7-2)]  timer = 5  room0_count=1; room1_count=2
[6,10]  [6,10]   timer = 6  room0_count=1; room1_count=2
[7,10]  [7,10]   timer = 7 ...
[8,10]  [8,10]
[9,10]  [9,10]
[10,10+(4-3)]

n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]

room 0, room 1, room 2
                            timer = 0
[1,20]                      timer = 1
[2,20]  [2,10]              timer = 2
[3,20]  [3,10]  [3,5]       timer = 3


n=2, meetings = [[1,8],[11,47],[23,41],[29,30],[30,33],[34,36],[43,44],[45,48]]
                                                        *
room 0, room 1
[8]                 timer = 1
...
[47]                timer = 11
[47]      [41]      timer = 23
[47]      [42]      timer = 41
[47]      [45]      timer = 42
[47]      [47]      timer = 45 
[48]
[]


'''
1331