Meeting Rooms III

'''
We are going to have two bucket 1.Free rooms 2.Used rooms so when we get a meeting while iterating on the meetings array, we will check is there any meeting room available and then we need to take the lesser number meeting room so we can make Free room bucket as min heap which will store the indices of the free rooms.
Now once we got the meeting room, then we will create a tuple ie. (end_time, room_index) where end_time will consider the delay also if it is there.

Now suppose while iterating the meetings array, we got a meeting but there is nothing in the free_rooms but there are chances that some meetings would have been already ended before the start of the current_meeting so we need to meetings from the used_rooms which ended in the increasing order(Top one should have the earliest ending) so we should make the used_rooms also as a min heap.we will pop the already over meeting and keep pushing into the free_rooms because we need to smallest index meeting room.

The final case, suppose there is no free_room even after removing the already over meetings and now we genuinely don't have any rooms available, then delay comes into the picture so top element of the used_rooms will be already having the earliest ending meeting(which is gonna end after the start time of current_meeting) so we will start the current meeting after that meeting gets over so we can pop the top element of the used_rooms and push the current meeting including the delay as end_time of popped meeting+duration of the current meeting.

for the most used room index, we can maintain an array of room count size, the moment you use any room, increase the value of that index
'''


from heapq import heappush,heappop
class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        free_rooms=[i for i in range(n)]
        used_rooms=[]
        meetings.sort()
        ans=[0]*n

        for i in range(len(meetings)):
            start=meetings[i][0]
            end=meetings[i][1]
            duration=end-start

            while len(used_rooms)>0 and used_rooms[0][0]<= start:
                end_time,index=heappop(used_rooms) #0th index denoted the meeting end time,and 1 denotes the room no
                heappush(free_rooms,index)

            if free_rooms:
                index=heappop(free_rooms)
                ans[index]+=1
                heappush(used_rooms, (end,index))
            else:
                end_time,index=heappop(used_rooms)
                new_end=end_time+ duration
                ans[index]+=1
                heappush(used_rooms,(new_end, index))

        k=0
        for i in range(len(ans)):
            if ans[i]>ans[k]:
                k=i
        return k