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

from heapq import heappush, heappop

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        """
        n: rooms
        meetings: List[[start:int, end:int]]
          - duration (end - start)

        fn (time) -> add free rooms to the room_heap
        state: free up times -> room indices

        fn () -> get next avail room and book (lowest index)
            - get next meeting
            - get duration
            - get next avail time
            - add room index to free_up[next_avail_time]
        state: heap of room indices (room_heap)

        xfn () -> get next avail time
        state: heap? of times

        state: counter meetings held by room {
            <room_num>: count
        }

        fn (new_count, room_idx) -> update max_count, max_count_room

        max_count: int
        max_count_room: room

        fn (meeting_idx, num meetings) -> end iteration

        return max_count_room
        """
        n_meetings = len(meetings)
        current_meeting = 0
        # print("assign meetings", n_meetings)

        meetings_heap = []
        for meeting in meetings:
            heappush(meetings_heap, meeting)

        # while len(meetings_heap) > 0:
        #     print(heappop(meetings_heap))

        free_up = {
            0: list(range(n))
        }
        room_heap = []
        time_heap = []
        time = 0

        room_booked_counter = {}
        max_count = float('-inf')
        max_count_room = None

        while current_meeting < n_meetings:
            # print(f"t={time} current_meeting={current_meeting} startend={meetings[current_meeting]}")
            # fn (time) -> add free rooms to the room_heap
            if time in free_up:
                for room_idx in free_up[time]:
                    heappush(room_heap, room_idx)

                del free_up[time]
            # print("room_heap")
            # print(room_heap)

            # if room is avilable -> assignment
            while len(room_heap) > 0:
                # fn () -> get next avail room and book (lowest index)

                # only assign room is time >= start
                peek_meeting_start, _ = meetings_heap[0]
                if time < peek_meeting_start:
                    # print(f"breaking t={time} start={peek_meeting_start}")
                    heappush(time_heap, peek_meeting_start)
                    break

                next_meeting_start, next_meeting_end = heappop(meetings_heap)

                next_room = heappop(room_heap)
                # a meeting of X duration is going to tie up the room
                # .: room is not available until (time + duration)
                duration = next_meeting_end - next_meeting_start
                next_avail_time = time + duration
                # print(f"nr={next_room} dur={duration} next_at={next_avail_time}")
                if next_avail_time not in free_up:
                    free_up[next_avail_time] = []
                free_up[next_avail_time].append(next_room)
                heappush(time_heap, next_avail_time)
                # print("time heap")
                # print(time_heap)

                if next_room not in room_booked_counter:
                    room_booked_counter[next_room] = 0
                room_booked_counter[next_room] += 1

                # fn (new_count, room_idx) -> update max_count, max_count_room
                new_count = room_booked_counter[next_room]
                if new_count > max_count:
                    max_count = new_count
                    max_count_room = next_room
                if new_count == max_count:
                    if max_count_room is None or next_room < max_count_room:
                        max_count_room = next_room

                # fn (meeting_idx, num meetings) -> end iteration
                current_meeting += 1
                if current_meeting == n_meetings:
                    break

            # todo use heap
            time = heappop(time_heap)
        
        return max_count_room
1431