Imagine we have a wizard that knows a few spells. Each spell has 3 attributes: Damage, cooldown time, and a cast time.

Cooldown time: the amount of time (t) it takes before being able to cast that spell again. A spell goes on "cooldown" the moment it begins casting.

Cast time: the amount of time (t) it takes to use a spell. While the wizard is casting something another spell cannot be cast and it cannot be canceled.

The question is: How would you maximize damage given different sets of spells?

It is easy to calculate the highest damage per cast time. But what about in situations where it is better to wait then to get "stuck" casting a low damage spell when a much higher one is available:

For example,

1) 100 damage, 1 second cast time, 10 second cool down.

2) 10 damage, 4 second cast time, 0 second cool down.

So, in this case you would cast #1, #2, wait. Cast #1

It is worth noting that, in extreme special cases, this problem degenerates to the Knapsack Problem, which is NP-complete to solve exactly. To see this, imagine that there is one spell, henceforth called the Megaspell, which does a very, very large amount of damage, has zero casting time, and has some positive cooldown $n$. If all the other spells do much less damage than the Megaspell, it will clearly be optimal to cast the Megaspell every $n$ seconds and then optimize the cooldown time with the weaker spells.

Now, assume all the other spells also have cooldown $n$. If one optimizes a given $n$-second downtime with these spells, then the same spell-sequence will also be possible in the next $n$-second downtime, and so we can assume the solution is $n$-periodic.

The problem then reduces to optimizing the $n$ available seconds with the lesser spells, each of which may only be cast once. If one replaces casting time with 'weight' and damage with 'value', one recovers the Knapsack Problem for maximum weight n.

I don't have an answer, but I just want to point out that the greedy algorithm fails. That is, if we choose to cast, at any point, the available spell which maximizes $\frac{ \text{damage} }{ \text{cast time} }$, we don't actually maximize our damage output because of cooldown. Consider the pair of spells $(300, 5, 12)$ and $(50, 3, 0)$ (where the three numbers are damage, cast time in second times, and cooldown time in seconds): the greedy algorithm suggests the casting schedule

• Cast spell 1 ($300$ damage, $5$ seconds),
• Cast spell 2 ($50$ damage, $3$ seconds),
• Cast spell 2 ($50$ damage, $3$ seconds),
• Cast spell 2 ($50$ damage, $3$ seconds),
• Repeat

which gives about $32.1$ damage per second. However, the casting schedule

• Cast spell 1 ($300$ damage, $5$ seconds),
• Cast spell 2 ($50$ damage, $3$ seconds),
• Cast spell 2 ($50$ damage, $3$ seconds),
• Wait $1$ second,
• Repeat

gives about $33.3$ damage per second. So a correct algorithm must take into account which spells are about to finish cooling down.

How about this algorithm? At each moment your decision is which spell to cast next. Having decided, if the cool down time for that one has expired, then go ahead and cast it. If not, wait until it has expired, then cast it. To make the decision, rank the spells in damage/time where time is from now to completion (including any cool down time left). Then see if you can fit in one of the other spell without delaying the best one. Taking Qiochu's example, at the start spell 1 is 300/5=60 dam/sec and spell 2 is 50/3=16.7dam/sec. Having cast spell 1, it is now 300/17=17.6 dam/sec, still better than 2. But we can get 2 done twice before 1 is available, so we should do that. The question would be whether you can change the parameters so that you should use the weaker spell even though it will delay the strong one by just a little bit.