Task scheduler

Source

You have a bunch of tasks to be executed on a single thread. Each is of a certain type in $\{1,2,\ldots,n\}$ and each takes exactly one second to finish. Tasks of the same type must be executed at least $k$ seconds apart. How long does it take to finish them all?

The greedy algorithm works naturally: at each second run the type with most remaining tasks that are allowed to be executed. However you don't necessarily need to produce execution order if only the total run time is asked. Can we find out the total idle seconds? It turns out to be simple.

Order the types by task count $a_1\leq a_2\leq \ldots \leq a_n$. There are at least $a_n-1$ chunks of $k-1$ or more seconds between execution of task $n$. Consider
$$
S=\sum_{i < n}\min\left(a_n-1, a_i\right).
$$

These are the tasks that we hope to squeeze in those $(a_n-1)(k-1)$ seconds. Apparently if
$$
S<(a_n-1)(k-1)
$$
then there will be at least $(a_n-1)(k-1)-S$ idle seconds, and not hard to see how to achieve exactly that.

Interestingly, TONCAS -- The Necessary Condition is Also Sufficient! If $S\geq (a_n-1)(k-1)$ then there will be no idle seconds. It could be proved by induction.