2402. Meeting Rooms III

Ideas

Heap comes to my mind when I know that I need to “schedule the earliest meeting” and “use smallest room index”.

The thinking process and some decisions we need to make:

1. when there is an available room, should we just take it?
   1. yes if we haven’t started any meeting
   2. else
      1. we might have some meeting rooms that were previously occupied but now ready to be used.
      2. so we need to make sure the every meeting that has ending time before current meeting are “cleared” and returned the room to our “available room pool”
2. after cleaning up the ended meetings, we have two scenarios.
   1. we have available room in the pool
      1. we use the smallest indexed room in the pool
   2. we do not have available room in the pool
      1. “time travel” to time when the next meeting ends
      2. use this time as the starting time to start the next meeting(remember to correctly process the end time here)

Surprisingly, we do not really need to keep a time variable to solve this, we can always use either the actual start time of a meeting, or the end time of the previous meeting + the duration of the current meeting to calculate the actual end time.

Algorithm

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        meetings.sort()
        having=[]
        rooms=[i for i in range(n)]
        heapq.heapify(rooms)
        counter=collections.defaultdict(int)
        for s,e in meetings:
            while having and having[0][0]<=s:
                ended=heapq.heappop(having)
                heapq.heappush(rooms,ended[1])
            if rooms:
                room=heapq.heappop(rooms)
                heapq.heappush(having,(e,room))
                counter[room]+=1
            else:
                ended=heapq.heappop(having)
                heapq.heappush(having,(ended[0]+e-s,ended[1]))
                counter[ended[1]]+=1
        max_i=None
        max_v=-1
        for k,v in counter.items():
            if v>max_v:
                max_i=k
                max_v=v
        return max_i