-
Notifications
You must be signed in to change notification settings - Fork 78
/
task_scheduler.py
44 lines (37 loc) · 1.34 KB
/
task_scheduler.py
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# coding: utf-8
"""
https://leetcode.com/problems/task-scheduler/
"""
from collections import Counter
from typing import List
import heapq
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
if n == 0:
return len(tasks)
recorded_tasks = []
queue = []
for task, count in Counter(tasks).items():
# heapq is min heap, so make count negative.
heapq.heappush(queue, (-count, task))
# We should schedule the most frequent tasks as frequently as possible.
while queue:
put_backs = []
for _ in range(n + 1):
if queue:
# Pop the current most frequent task.
count, task = heapq.heappop(queue)
# We don't need to check whether the popped task is in recorded_tasks[-n:] or not.
recorded_tasks.append(task)
count += 1
if count < 0:
put_backs.append((count, task))
else:
if put_backs:
recorded_tasks.append('idle')
else:
break
for task_data in put_backs:
heapq.heappush(queue, task_data)
# print(recorded_tasks)
return len(recorded_tasks)