CODEWITHSUNDEEP
algorithmgreedy
Jayden Rice
Jayden Rice

Reputation: 301

Interval Scheduling Problem: accepting requests in order of latest starting time is always optimal?

I learned that the interval scheduling problem is optimal when we accepts the requests in the order of earliest finish time.

Then, is it also true that we also have always optimal solution if we accept the requests in the order of latest starting time?

I think it is false, because we would get a different schedule set, but I am wondering how I can come up with a more mathematical proof.

Upvotes: 1

Views: 1630

Answers (2)

templatetypedef
templatetypedef

Reputation: 372714

As a hint, imagine mirroring all the intervals, or pretending that time runs backwards. You know that the greedy “take the earliest finish time” will select the maximum number of intervals. If you sweep backwards in time, what’s the equivalent condition?

Upvotes: 0

Matt Timmermans
Matt Timmermans

Reputation: 59144

Scheduling by latest starting time is the same as:

  1. Reverse time (negate all the times and swap interval ends)
  2. Schedule by earliest finish time
  3. Reverse time again to restore the original intervals.

By symmetry, the maximum number of schedulable intervals is the same whether you reverse time or not, so if "earliest finish time" is optimal, then "latest start time" is optimal, too.

Upvotes: 1

Related Questions