Re: [閒聊] 每日leetcode
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
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.253 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1728614388.A.AB1.html
討論串 (同標題文章)
完整討論串 (本文為第 973 之 1554 篇)：