0

Given intervals e.g. (1,3) (2,4) (3,6) (4,7), find schedule such that no conflicts exist, AND the total length of intervals scheduled is maximal.

I've studied "Interval Scheduling" type of questions when they talk about topics such as Greedy solutions & Dynamic programming in school.I know that the solutions vary depends on the specific goal for scheduling, for e.g.: schedule as many intervals as possible ==> Greedy.

But for this question, i think we'll have to resort to brute force(enumerate)? please advise

DanSoren
  • 173
  • 2
  • 9
  • 1
    Look here: http://stackoverflow.com/questions/24026073/algorithm-to-find-maximum-coverage-of-non-overlapping-sequences-i-e-the-weig – pkacprzak Apr 18 '16 at 00:37
  • cool. So this should be equivalent to "weighted interval sched" where weight equals to interval durations? – DanSoren Apr 18 '16 at 00:45

1 Answers1

0

Your proposed problem can still be solved in a greedy approach. Since you've known of the original interval scheduling problem, I'll make the solution based upon what you mentioned in the question statement.

Step 1: Sort intervals based on start time.

Step 2: Maintain a "spawn" pool which uses a 2-tuple heap to maintain the data structure.

To be more precise in step 2, let's assume we have N sorted intervals I[0] ... I[N-1], each I has a start and a stop attributes, so I[i].start <= I[i+1].start. You have a 2-tuple heap, each tuple represents (T, M). T means time to leave the heap, or equivalently, the stop time of the interval; M represents the maximum current coverage if this interval is chosen. Note the order of heap is maintained by T. A variable ANS is maintained, which keeps the current maximum coverage. Thus, the algorithm runs like this:

ANS <- 0
HEAP <- [empty]
for each sorted intervals `I[i]`:
    while HEAP.empty() == false && HEAP.first_element.T < I[i].start
        TMP = HEAP.first_element
        HEAP.pop_first_element
        if TMP.M > ANS
            ANS = TMP.M
    HEAP.insert((I[i].stop, ANS + I[i].stop - I[i].start))
TimeString
  • 1,778
  • 14
  • 25