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 log n) and needs only O(n) memory. In fact, the running time is O(ng~* log n), where g~* is the minimum number of gaps.
展开▼
