871. Scheduling With a Cooldown
A processor runs n tasks, each labelled by an uppercase letter. Two tasks
with the SAME label must be separated by at least c time units of other work
or idling. Each task takes one unit.
Print the least total time to run every task.
The greedy rule is to always run the label with the most remaining work that is not cooling down, which is a repeated "give me the largest" and therefore a heap.
There is also a formula. The most frequent label, appearing f times, forces
f - 1 gaps of c + 1 units, plus one unit for each label tied at that
frequency. The answer is the larger of that and n, because when there are
many distinct labels the gaps fill themselves and no idling is needed.
Knowing both matters: the heap generalises and the formula is what an interviewer wants you to derive.
Constraints - `1 ≤ n ≤ 100000` - `0 ≤ c ≤ 100` - Every label is a single uppercase English letter.
Input
The first line contains two integers n and c.
The second line contains n space-separated uppercase letters, the task labels.
Output
Print one integer: the least total time, counting idle units.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.