What is the time complexity of the optimal Task Scheduler algorithm using a max-heap for t total tasks and m unique tasks?

medium🪤 Complexity Trap Q13 of Q15

Greedy Algorithms - Task Scheduler (CPU Cooling)

What is the time complexity of the optimal Task Scheduler algorithm using a max-heap for t total tasks and m unique tasks?

AO(t log m) because each task is pushed and popped from a heap of size up to m

BO(t + m) because counting frequencies and scheduling are linear

CO(m log t) because heap operations depend on total tasks

DO(t * m) because each task may be compared with all unique tasks

Step-by-Step Solution

Step 1: Analyze heap operations
Heap size is at most m (unique tasks). Each task is pushed and popped at most once per execution.
Step 2: Calculate total operations
For t tasks, each heap operation costs O(log m), so total is O(t log m).
Final Answer:
Option A -> Option A
Quick Check:
Heap size depends on unique tasks, not total tasks [OK]

Quick Trick: Heap operations scale with unique tasks, not total tasks [OK]

Common Mistakes:

MISTAKES

Trap Explanation:

PITFALL

Option A looks plausible as tasks relate to unique tasks, but heap operations cost log m per task.

Interviewer Note:

CONTEXT

Checks if candidate understands heap complexity and distinguishes total vs unique tasks.

Master "Task Scheduler (CPU Cooling)" in Greedy Algorithms

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

More Greedy Algorithms Quizzes