LeetCode 621. 任务调度器 - Python
原题链接
中等
作者:
小聂同学
,
2023-10-09 05:29:00
,
所有人可见
,
阅读 55
import heapq
from collections import Counter
class Solution:
'''
Question:
input - tasks, list[str], tasks list, list can't be null
- n, int, idle time needed
output - int, the least number of times
Main Idea: Heap
Use max heap - store -cnt of tasks remaining to process
Use queue - (-cnt, idle_time), idle_time means when we can process this task again
Time Complexity: O(m*n), n is size of tasks, m is the idle_time
times is the length of the loop, worst case tasks*idle_time
Space Complexity: O(n)
'''
def leastInterval(self, tasks: List[str], n: int) -> int:
count = Counter(tasks)
max_heap = [-cnt for cnt in count.values()]
heapq.heapify(max_heap)
time = 0
q = deque()
while max_heap or q:
time +=1
if max_heap:
cnt = 1 + heapq.heappop(max_heap)
if cnt:
q.append([cnt, time + n])
# Check head of queue
if q and q[0][1] == time:
heapq.heappush(max_heap, q.popleft()[0])
return time