What is the problem if we sort the intervals according to their finishing time like the interval scheduling problem? Could someone give a counterexample ?

Note- (refer here for detailed definition)

Interval Partioning Problem: Multiple Identical Resources are available and we have to partition all intervals across these resources using as few as possible. On each resource all intervals should be non overlapping.

Interval Scheduling Problem: Only one resource is available. We have to maximise the number of non-overlapping intervals we can use on that single resource.

  • 1
    $\begingroup$ You should be the one looking for counterexample. If you think that sorting according to finishing time should also work, you should try to prove that it does. $\endgroup$ – Yuval Filmus Sep 16 '16 at 21:22
  • 1
    $\begingroup$ I did try to prove it- I'm not sure whether I got it right. This is not a homework problem btw-just a question that I was thinking about. $\endgroup$ – user1968919 Sep 16 '16 at 23:41
  • 2
    $\begingroup$ This is answered here: stackoverflow.com/a/35421794/940550. $\endgroup$ – Yuval Filmus Sep 17 '16 at 4:12
  • 2
    $\begingroup$ cs.stackexchange.com/q/59964/755 $\endgroup$ – D.W. Sep 17 '16 at 4:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.