August 2nd, 2007, 02:46 PM
Join Date: Aug 2007
Time spent in forums: 5 m 43 sec
Reputation Power: 0
Help on a proof for my greedy algorithm
Hi, I was wondering if anyone could help me prove my algorithm for the problem below.
My greedy algorithm looks for the most conflicts:
R = set of all intervals
A = empty set
while R is not empty
choose i in R s.t. it has the most conflicts
Add i to A
Remove i and all other intervals it has conflicts with from R
I'm pretty sure this algorithm works, I just can't get my proof for it exactly right. If anyone can help, that'd be great!
The following problem is below:
The manager of a large student union on campus comes to you with the following
problem. She’s in charge of a group of students, each of whom is scheduled to work one
shift during the week. There are different jobs associated with these shifts , but we can
view each shift as a single contiguous interval of time. There can be multiple shifts going
on at once. The manager is trying to find a subset of these students to form a supervising
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, the student 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 is 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.