Refined algorithms for hitting many intervals

Within a study of scheduling problems with gaps, Chrobak et al. (CIAC 2015) have shown how to find γ points on the line that hit a maximum number of intervals, in a given family of n intervals, in O(γn2) time. The problem is equivalent to finding γ cliques in an interval graph that cover a maximum number of distinct vertices. We give refined algorithms that run faster if the interval graph of the family is sparse.