621. Task Scheduler

Task Scheduler (LeetCode 621) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Greedy Patterns pattern, in the Task Scheduling (Frequency Based) subpattern.

• NeetCode 150 · #65 of 150 · Heap / Priority Queue
• NeetCode 250 · #115 of 250 · Heap / Priority Queue

How to solve Task Scheduler

Task Scheduler is a Task Scheduling problem, part of Greedy Patterns. Schedule tasks with cooldown using frequency-based greedy approach.

Work towards the solution in these steps:

1. There are many different solutions for this problem, including a greedy algorithm.
2. For every cycle, find the most frequent letter that can be placed in this cycle. After placing, decrease the frequency of that letter by one.
3. Use Priority Queue.

The reference solution runs in O(N) time and O(1) space.

The Task Scheduler solution and editorial walks through the full approach with reference code.

Problem statement

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. Tasks can be completed in any order, but there's a constraint: there has to be a gap of at least n intervals between two tasks with the same label.

Return the minimum number of CPU intervals required to complete all tasks.

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2

Output: 8

Explanation: A possible sequence is: A -> B -> idle -> A -> B -> idle -> A -> B.

After completing task A, you must wait two intervals before doing A again. The same applies to task B. In the 3rd interval, neither A nor B can be done, so you idle. By the 4th interval, you can do A again as 2 intervals have passed.

Example 2:

Input: tasks = ["A","C","A","B","D","B"], n = 1

Output: 6

Explanation: A possible sequence is: A -> B -> C -> D -> A -> B.

With a cooling interval of 1, you can repeat a task after just one other task.

Example 3:

Input: tasks = ["A","A","A", "B","B","B"], n = 3

Output: 10

Explanation: A possible sequence is: A -> B -> idle -> idle -> A -> B -> idle -> idle -> A -> B.

There are only two types of tasks, A and B, which need to be separated by 3 intervals. This leads to idling twice between repetitions of these tasks.

Constraints:

- 1 <= tasks.length <= 104

- tasks[i] is an uppercase English letter.

- 0 <= n <= 100

Topics and companies

Topics: Array, Hash Table, Greedy, Sorting, Heap (Priority Queue), Counting.

Reported in interviews at Facebook, Rubrik, Amazon, Pinterest, Google, Microsoft, Bloomberg, Airtel.

How to practise Task Scheduler on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N) time and O(1) space.

Open Task Scheduler in the code editor, or read the Task Scheduler editorial for a worked solution with its approach and complexity analysis.

Where Task Scheduler sits in the DSA pattern sheet

• Greedy Patterns pattern guide
• Task Scheduling (Frequency Based) subpattern
• The full DSA patterns sheet

Problems related to Task Scheduler

Other problems that use the same Task Scheduling (Frequency Based) and Greedy Patterns techniques:

• Distant Barcodes — Medium, same subpattern
• Dota2 Senate — Medium, same subpattern
• Assign Cookies — Easy, same pattern
• Candy — Hard, same pattern
• Car Pooling — Medium, same pattern
• Divide Intervals Into Minimum Number of Groups — Medium, same pattern

Task Scheduler FAQ