Loading...
Loading...
Loading...
Before semester exams, Arjun plans his revision in time slots. He has m tasks, each marked with a subject letter from A to Z. Each slot he either does one task or rests.
To avoid getting bored, after a task of some subject he must wait at least n slots before doing that subject again. Other subjects or rest can fill those slots. The tasks can be done in any order.
Print the fewest slots needed to finish all m tasks.
Example 1
Input
6 2 A A A B B B
Output
8
One best plan is A B rest A B rest A B, which takes 8 slots.
Example 2
Input
7 2 A A A B C D E
Output
7
A B C A D E A uses every slot, so no rest is needed: 7 slots.
Try the problem first. Open one hint at a time.
The subject with the most tasks left decides how many rest slots you need. Do it as early as you can.
Plan in rounds of n + 1 slots. In each round, do one task from each of the n + 1 subjects with the most tasks left.
A heap of counts gives you the busiest subjects quickly. Put the reduced counts back only after the round ends.
A full round costs n + 1 slots, but the very last round costs only the tasks done in it.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor