1942. The Number of the Smallest Unoccupied Chair ## 思路 先把times轉成 (start/end time, event_state, idx) 的time_heap 照時間順序檢查 如果state是-1, 就釋出椅子到min heap (free_chairs) 如果state是1, 就從free_chairs拿最小的椅子或是拿一張新椅子 ## Code ```python class Solution: def smallestChair(self, times: List[List[int]], targetFriend: int) -> int: time_heap = [] for idx, (start, end) in enumerate(times): heapq.heappush(time_heap, (start, 1, idx)) heapq.heappush(time_heap, (end, -1, idx)) free_chairs = [] chair_mapping = {} max_idx = 0 while time_heap: time, state, idx = heapq.heappop(time_heap) if state == -1: chair_idx = chair_mapping[idx] heapq.heappush(free_chairs, chair_idx) continue if free_chairs: chair_idx = heapq.heappop(free_chairs) else: chair_idx = max_idx max_idx += 1 if idx == targetFriend: return chair_idx chair_mapping[idx] = chair_idx return -1 ``` -- https://i.imgur.com/kyBhy6o.jpeg -- ※ 發信站: 批踢踢實業坊(pttbestweb.org.tw), 來自: 185.213.82.253 (臺灣) ※ 文章網址: https://pttbestweb.org.tw/Marginalman/M.1728614388.A.AB1