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 $$O(n^4)$$O(n4) and requiring $$O(n^3)$$O(n3) 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 $$O(n^2 \log n)$$O(n2logn) and needs only O(n) memory. In fact, the running time is $$O(n (g^*+1)\log n)$$O(n(gź+1)logn), where $$g^*$$gź is the minimum number of gaps.