August 2nd, 2007, 02:46 PM
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.
August 9th, 2007, 12:42 PM
you can't be sure about its correctness if don't prove it. Actually your algorithm is not correct, this can be seen on this simple test-case:
number 4 has 4 conflicts, but if we choose it, the we'll have to choose number 1 and number 7 too. So we would rather choose number 3 and number 5.
4. -------------------- (4)
This problem does require a greedy algorithm. You should not count conflicts, but you have to sort the intervals with respect to their left or right ends and process them step by step. I will write the exact algorithm if you wish.
Last edited by Michael88; August 9th, 2007 at 12:45 PM.
August 9th, 2007, 12:52 PM
I figured it out a few days ago. Thanks for reply though!
February 1st, 2012, 10:44 AM
Could someone help me out with this? I'm still having trouble after sorting the set of student shifts by the earliest start time or the earliest finish time. Each greedy criteria seems to fail on one or more test cases that I have.
Any hints would be greatly appreciated.