iLoveIOI's blog

Interval scheduling with K machines
By iLoveIOI, history, 5 years ago, In English

How do I solve the interval scheduling problem but instead with k machines, meaning I can put the intervals in K different sets such that in each of the sets none of the intervals overlap and I want the maximum total interval, in O(nlogn) time or less.

Thanks!

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I think is the problem you are refferring to ??! CSES Problem

The approach is the same for the question with only one machine the only difference here is as you proceed assigning every interval(sorted as per the ending time) you assign it to the machine which ended it's last job just before the start of this job. This ensures that as soon as a machine gets free it is assigned the next available job. You can see the C++ implementation here.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why might it not be optimal to pick the first K elements at first and then proceed with the assignment.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      whether it will be optimal or not depends on how you proceed and even in the above solution the first k elements are always being picked but not nessesarily by different machines.

      Consider the test case

      n = 3, k = 2
Intervals :
1 2
2 3
1 5

      here the optimal solution would be

      machine 1: (1,2), (2,3)
machine 2: (1,5)

      but if you greedily give the first 2 intervals to different machines the output will be : 

      machine 1: (1,2)
machine 2: (2,3)
      → Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

This lecture note from the University of Toronto answers your question: http://www.cs.toronto.edu/~milad/csc373/lectures/T1.pdf

→ Reply