A Greedy Approximation Algorithm for Minimum-Gap Scheduling

We consider scheduling of unit-length jobs with release times and deadlines to minimize the number of gaps in the schedule. The best algorithm for this problem runs in time O(n 4) and requires O(n 3) memory. We present a simple greedy algorithm that approximates the optimum solution within a factor of 2 and show that our analysis is tight. Our algorithm runs in time O(n 2 logn) and needs only O(n) memory. In fact, the running time is O(n g ∗ logn), where g ∗ is the minimum number of gaps.