621. Task Scheduler

Posted on Edited on In

621. Task Scheduler

Description

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:

1
2
3
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 3^rd interval, neither A nor B can be done, so you idle. By the 4^th interval, you can do A again as 2 intervals have passed.

Example 2:

1
2
3
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:

1
2
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 <= 10^4
  • tasks[i] is an uppercase English letter.
  • 0 <= n <= 100

Hints/Notes

  • 2024/12/27
  • greedy
  • No solution from 0x3F

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        int count[26]{};
        for (auto task : tasks) {
            count[task - 'A']++;
        }
        map<int, int> m;
        int maxFreq = 0;
        for (int i = 0; i < 26; i++) {
            if (count[i] > 0) {
                m[count[i]]++;
            }
            maxFreq = max(maxFreq, count[i]);
        }
        if (m[maxFreq] > n) {
            return tasks.size();
        } else {
            return max((maxFreq - 1) * (n + 1) + m[maxFreq], (int)tasks.size());
        }

    }
};