Task Scheduler — LeetCode 621 Python Solution
MediumGreedyArrayHash TableCountingSortingHeap (Priority Queue)
- Problem
- #621
- Pattern
- Heap / Priority Queue
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are given an array of CPU tasks, each labeled with a letter from A to Z, and a number n. Each CPU interval can be idle or allow the completion of one task.
Python solution
Python
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
cnt = Counter(tasks)
x = max(cnt.values())
s = sum(v == x for v in cnt.values())
return max(len(tasks), (x - 1) * (n + 1) + s)Complexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 621. Task Scheduler is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
On study lists
This problem is on NeetCode 150 and Grind 75.
Frequently asked questions
- How hard is LeetCode 621. Task Scheduler?
- LeetCode 621. Task Scheduler is rated Medium on LeetCode.
- What is the time complexity of LeetCode 621. Task Scheduler?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 621. Task Scheduler?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 621. Task Scheduler cover?
- LeetCode 621. Task Scheduler is tagged Greedy, Array, Hash Table, Counting, Sorting and Heap (Priority Queue) on LeetCode.