#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2007
    Posts
    2
    Rep 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
    End while
    Return A

    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.
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2005
    Posts
    57
    Rep Power
    17
    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:

    Code:
    1.----------(2)
    2.                       -------(2)
    3.      --------------------(3)
    4.                        -------------------- (4)
    5.                                         --------------------(3)
    6.                                         ----------(2)
    7.                                                               ---------(1)
    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.

    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 01:45 PM.
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2007
    Posts
    2
    Rep Power
    0
    I figured it out a few days ago. Thanks for reply though!
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2012
    Posts
    1
    Rep Power
    0
    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.

    Thanks.

IMN logo majestic logo threadwatch logo seochat tools logo