<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:
        # first need to sort the array from the left
        meetings.sort(key = lambda x: x[0])
        
        count = 0
        meeting_room = [0]*n

        #connected_array = [intervals[0]]
        ending_time = [[i,0] for i in range(n)]
        #ending_time = [[0,intervals[0][1]]] # first element is the room number, second is the ending time
        #print('first', meetings)
        if len(meetings) == 1:
            return 0

        length = len(meetings)
        for i in range(length):
            left, right = meetings[i][0], meetings[i][1]
            #print('r l', left, right)
            # we sort the connected array from the right
            #connected_array.sort(key = lambda x: x[1])
            ending_time.sort(key = lambda x: x[1]) # sort by the ending time
            ending_time_list = [ending_time[j][1] for j in range(len(ending_time))]
            #print('meeting ending time', ending_time_list)
            #print('ending time before', ending_time)
            if left > max(ending_time_list): # take the one with least room number
                ending_time.sort(key = lambda x: x[0])
                ending_time[0][1] = right
                meeting_room[ending_time[0][0]] += 1
                continue

            if left < min(ending_time_list): # all rooms are occupaid, then wait and delay, we can directly added to the minimum meeting room
                meetings[i] = [min(ending_time_list), min(ending_time_list) + right - left]
                left, right = min(ending_time_list), min(ending_time_list) + right - left
                # meetings.sort(key = lambda x: x[0])
                # ending_time.sort(key = lambda x: x[1]) # sort by the ending time
                # ending_time_list = [ending_time[j][1] for j in range(len(ending_time))]
                # left, right = meetings[i][0], meetings[i][1]
                #print('ite', meetings)
            # find the earlist to insert
            #print('before sort', ending_time, meetings, ending_time)

            length1 = len(ending_time)
            j, find = 0, 0
            room_index = [ending_time[j][0] for j in range(len(ending_time))]

            temp_ending_time = [k for k in ending_time if k[1] <= left ]
            temp_ending_time.sort(key = lambda x: x[0]) # sort
            #print('temp', temp_ending_time)
            ending_time[room_index.index(temp_ending_time[0][0])][1] = right
            meeting_room[temp_ending_time[0][0]] += 1

            
            # while j < length1 and find != 1:
            #     #print(j)
            #     index = room_index[j]
            #     ending_temp = ending_time[j][1]
            #     if ending_temp <= left: # we then need to check if the next one is still the same
            #         if j + 1 < length1 and ending_time[j+1][1] <= left:
            #             # then check the room number
            #             #print('check', ending_time[room_index[j+1]][0], ending_time[room_index[j]][0])
            #             if ending_time[j+1][0] < ending_time[j][0]:
            #                 j += 1
            #                 continue
            #         #print('ind', index)
            #         ending_time[j][1] = right # update the ending_time
            #         meeting_room[index] += 1 # count the meeting
            #         find = 1
            #     j += 1
            #print('ending time after', ending_time)
            #print(meeting_room)

        #print(meeting_room)
        index = 0
        min_ = 0
        for room in range(len(meeting_room)):
            num_me = meeting_room[room]
            if num_me > min_:
                min_ = num_me
                index = room
        return index
61500