4.2. Scheduling to Minimize Lateness: An Exchange Argument

We have a single resource and a set of n requests to use the resource

The resource has a deadline d _i and requires a contiguous interval of time t _i

Each request is flexible: It can be scheduled at any time before its deadline.

Each accepted request is assigned an interval of length t _i , and different requests are assigned nonoverlapping intervals

Let S = the overall start time

Each request i is assigned an interval of time of length t _i = [ S(i),fi)] where f(i) = S(i)+ t(i)