Editorial for IOI '02 P4 - Batch Scheduling
Submitting an official solution before solving the problem yourself is a bannable offence.
This problem can be solved using dynamic programming. Let be the minimum total cost of all partitionings of jobs into batches. Let be the minimum total cost when the first batch is selected as . That is, .
Then we have that
- for ,
- and .
The time complexity of the above algorithm is .
Investigating the property of , P. Bucker  showed that this problem can be solved in time.
From , we have that for ,
Let and .
Property 1: Assume that for . Then .
Property 2: Assume for some . Then for each with , or .
Property 2 implies that if for , is not needed for computing . Using this property, a linear time algorithm can be designed, which is given in the following.
The algorithm calculates the values for down to . It uses a queue-like list with tail and head satisfying the following properties:
- — (1)
When is calculated,
// Using , remove unnecessary element at head of .
If , delete from since for all , and by Property 1.
Continue this procedure until for some , .
Then by Property 1, for or and contains only .
Therefore, is equal to .
// When inserting at the tail of , maintain for the condition (1) to be satisfied.
If , delete from by Property 2.
Continue this procedure until .
Append as a new tail of .
Each is inserted into and deleted from at most once. In each insertion and deletion, it takes a constant time. Therefore the time complexity is .