## Editorial for IOI '02 P4 - Batch Scheduling

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
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 .

#### Time Algorithm

The time complexity of the above algorithm is .

#### Time Algorithm

Investigating the property of , P. Bucker [1] 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.

##### Algorithm Batch

The algorithm calculates the values for down to . It uses a queue-like list with tail and head satisfying the following properties:

• and
• — (1)

When is calculated,

1. // 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 .

2. // 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 .

##### Analysis

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 .