Variant Scheduling Algorithm

Question

I'm working on a problem from "Algorithm Design" by Kleinberg, specifically problem 4.15. I'm not currently enrolled in the class that this relates to -- I'm taking a crack at the problem set before the new quarter starts to see if I'd be able to do it. The question is as follows:

The manager of a large student union on campus comes to you with the
following problem. She’s in charge of a group of n students, each of whom
is scheduled to work one shift during the week. There are different jobs
associated with these shifts (tending the main desk, helping with package
delivery, rebooting cranky information kiosks, etc.), but.we can view each
shift as a single contiguous interval of time. There can be multiple shifts
going on at once.

She’s trying to choose a subset of these n students to form a super-
vising committee that she can meet with once a week. She considers such
a committee to be complete if, for every student not on the committee,
that student’s shift overlaps (at least partially) the shift of some student
who is on the committee. In this way, each student’s performance can be
observed by at least one person who’s serving on the committee.
Give an efficient algorithm that takes the schedule of n shifts and
produces a complete supervising committee containing as few students
as possible.

Example. Suppose n = 3, and the shifts are
Monday 4 p.M.-Monday 8 P.M.,
Monday 6 p.M.-Monday 10 P.M.,
Monday 9 P.M.-Monday 1I P.M..

Then the smallest complete supervising committee would consist of just
the second student, since the second shift overlaps both the first and the
third.

My attempt (I can't find this problem in my solution manual, so I'm asking here):

    Construct a graph G with vertices S1, S2, ..., Sn for each student. 
Let there be an edge between Si and Sj iff students i and j have an overlapping 
shift. Let C represent the set of students in the supervising committee.

[O(n + 2m) to build an adjacency list, where m is the number of shifts? 
Since we have to add at least each student to the adjacency list, and add an 
additional m entries for each shift, with two entries added per shift since 
our graph is undirected.]

Sort the vertices by degree into a list S [O(n log n)].

While S[0] has degree > 0:
    (1) Add Si to C. [O(1)]
    (2) Delete Si and all of the nodes that it was connected to, update the 
adjacency list.
    (3) Update S so that it is once again sorted.
Add any remaining vertices of degree 0 to C.

I'm not sure how to quantify the runtime of (2) and (3). Since the degree of any node is bounded by n, it seems that (2) is bounded by O(n). But the degree of the node removed in (1) also affects the number of iterations performed inside of the while loop, so I suspect that it's possible to say something about the upper bound of the whole while loop -- something to the effect of "Any sequence of deletions will involve deleting at most n nodes in linear time and resorting at most n nodes in linear time, resulting in an upper bound of O(n log n) for the while loop, and therefore of the algorithm as a whole."

Answer 1

You don't want to convert this to a general graph problem, as then it's simply the NP-hard vertex cover problem. However, on interval graphs in particular, there is in fact a linear-time greedy algorithm, as described in this paper (which is actually for a more general problem, but works fine here). From a quick read of it, here's how it applies to your problem:

• Sort the students by the time at which their shift ends, from earliest to latest. Number them 1 through n.
• Initialize a counter k = 1 which represents the earliest student in the ordering not in the committee.
• Starting from k, find the first student in the order whose shift does not intersect student k's shift. Suppose this is student i. Add student i-1 to the committee, and update k to be the new earliest student not covered by the committee.
• Repeat the previous step until all students are covered.

(This feels correct, but like I said I only had a quick read, so please say if I missed something)