Question 3:

Given a gas station with two pumps, and a collection of cars

S

=

{

1

,

2

, . . . , n

}

with filling time

s

i

for item

i

(on both pumps). Give an algorithm that divides

S

to

two disjoint sets

A, B

,

A

B

=

S

so that if

A

is pumped on the first pump and

B

on the second pump (in parallel) the finishing time of the pump that finished last is

minimum.