Greedy Algorithms - Task Scheduler (CPU Cooling)
What is the overall time complexity of the Task Scheduler algorithm that uses a frequency map and a max-heap to schedule
t tasks with m unique task types?What is the overall time complexity of the Task Scheduler algorithm that uses a frequency map and a max-heap to schedule t tasks with m unique task types?
medium📊 Complexity Q5 of Q15
Step-by-Step Solution
Solution:
Step 1: Build frequency map
Counting frequencies takes O(t) time.Step 2: Build max-heap of size m
Heap construction is O(m).Step 3: Scheduling tasks
Each task is pushed and popped from the heap at most once, costing O(log m) per operation.Step 4: Total complexity
Overall complexity is O(t log m) dominated by heap operations over all tasks.Final Answer:
Option B -> Option BQuick Check:
Heap operations scale with unique tasks, repeated for all tasks [OK]
Quick Trick: Heap operations per task lead to O(t log m) complexity [OK]
Common Mistakes:
MISTAKES- Assuming complexity depends on total tasks squared
- Confusing m and t in log factors
Trap Explanation:
PITFALL- Mistaking total tasks for unique tasks in heap operations
Interviewer Note:
CONTEXT- Tests understanding of algorithmic complexity with heaps
Master "Task Scheduler (CPU Cooling)" in Greedy Algorithms
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Greedy Algorithms Quizzes