How do you solve Task Scheduler on LeetCode?

Task Scheduler (LeetCode #621) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Understanding task frequency is crucial to optimizing the scheduling.

What is the brute force solution for Task Scheduler?

The brute force approach for Task Scheduler is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach tries every possible sequence of tasks while ensuring that the constraints are met. This means we will generate all permutations of the tasks and check each one for validity, which is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Task Scheduler?

Always clarify the constraints before diving into the solution. Think about edge cases, such as when n is larger than the number of tasks. Practice explaining your thought process as you code.

What are common mistakes when solving Task Scheduler?

Failing to account for tasks with the same maximum frequency. Not considering idle time when calculating total intervals.

#621

Task Scheduler

Medium

ArrayHash TableGreedySortingHeap (Priority Queue)CountingHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution uses a greedy approach to maximize the usage of the CPU while respecting the cooling interval. We prioritize tasks based on their frequency and fill the idle slots as needed.

⚙️

Algorithm

4 steps

1Step 1: Count the frequency of each task using a HashMap.
2Step 2: Identify the maximum frequency and how many tasks have that frequency.
3Step 3: Calculate the total intervals required using the formula: (max_freq - 1) * (n + 1) + tasks_with_max_freq.
4Step 4: Return the maximum of total intervals and the length of the tasks array.

solution.py8 lines

1from collections import Counter
2
3def leastInterval(tasks, n):
4    task_counts = Counter(tasks)
5    max_freq = max(task_counts.values())
6    max_count = sum(1 for count in task_counts.values() if count == max_freq)
7    total_intervals = (max_freq - 1) * (n + 1) + max_count
8    return max(total_intervals, len(tasks))

ℹ

Complexity note: The time complexity is O(n) due to counting the tasks and calculating the intervals, which is efficient for this problem.

1Understanding task frequency is crucial to optimizing the scheduling.
2The cooling interval n directly affects how tasks can be arranged.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.