Practice › Heap & Priority Queue
Task Scheduler
Medium · Heap & Priority Queue · Asked at Meta, Amazon, Microsoft, Uber
A CPU runs tasks (uppercase letters), one per time unit, or stays idle. Two runs of the same task must be at least n time units apart (n other units between them). Print the minimum number of time units to finish all tasks.
Input
First line: the tasks as a string of uppercase letters. Second line: n.
Output
The minimum number of time units.
Constraints
- 1 ≤ number of tasks ≤ 10^4
- 0 ≤ n ≤ 100
Formula: with f = highest frequency and c = how many tasks have it, the answer is max(total, (f − 1)(n + 1) + c). A max-heap simulation gives the same result.
Example 1
Input
AAABBB 2
Output
8
Example 2
Input
ACABDB 1
Output
6
Hints
- Only the counts matter. The most frequent task decides how many "frames" of length n + 1 you need.
- With f = the highest count and c = the number of tasks having it: answer = max(total tasks, (f − 1)·(n + 1) + c).
Approach
Lay out the most frequent task f times with n gaps after each of the first f − 1 copies: that creates (f − 1)(n + 1) slots plus a final row holding every task that also has count f (c of them). Other tasks fill the gaps. If there are more tasks than slots, no idling is needed at all and the answer is simply the number of tasks. Hence max(total, (f − 1)(n + 1) + c). A max-heap simulation produces the same number.
Complexity: O(total) time · O(26) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
string tasks;
long long n;
cin >> tasks >> n;
vector<long long> cnt(26, 0);
for (char c : tasks) cnt[c - 'A']++;
long long f = *max_element(cnt.begin(), cnt.end());
long long c = count(cnt.begin(), cnt.end(), f);
cout << max((long long)tasks.size(), (f - 1) * (n + 1) + c) << "\n";
return 0;
}Python solution
import sys
from collections import Counter
data = sys.stdin.read().split()
tasks, n = data[0], int(data[1])
cnt = Counter(tasks)
f = max(cnt.values())
c = sum(1 for v in cnt.values() if v == f)
print(max(len(tasks), (f - 1) * (n + 1) + c))Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String tasks = sc.next();
long n = sc.nextLong();
long[] cnt = new long[26];
for (char ch : tasks.toCharArray()) cnt[ch - 'A']++;
long f = 0, c = 0;
for (long v : cnt) f = Math.max(f, v);
for (long v : cnt) if (v == f) c++;
System.out.println(Math.max(tasks.length(), (f - 1) * (n + 1) + c));
}
}