A greedy approximation algorithm for minimum-gap scheduling

摘要

We consider scheduling of unit-length jobs with release times and deadlines, where the objective is to minimize the number of gaps in the schedule. Polynomial-time algorithms for this problem are known, yet they are rather inefficient, with the best algorithm running in time and requiring memory. We present a greedy algorithm that approximates the optimum solution within a factor of 2 and show that our analysis is tight. Our algorithm runs in time and needs only O(n) memory. In fact, the running time is , where is the minimum number of gaps.