In the \"Interval Scheduling\" Problem, there is a single resource and many requ

Question

In the "Interval Scheduling" Problem, there is a single resource and many requests in the form of time intervals, so we must choose which requests to accept and which to reject.

In the "Scheduling all Intervals" Problem, a related problem arises if we have many identical resources available and we wish to schedule all the requests’ using as few resources as possible. Because the goal here is to partition all intervals across multiple resources.

Provide a counter-example to show that the “earliest finish time first” leads to a non-optimal solution for the “Scheduling All Intervals” problem

Explanation / Answer

In interval Scheduling problem when we consider earliest time first it ignore the strat time order. But if we have multiple resources we can run two processes on two resources symoultaneosly if their start time is same also. Now consider the example : P1 P2 P3 P4 P5 P6 P7 P8 (1-6) (2-5) (3-8) (4-12) (5-6) (7-9) (8-11) (10-12) And Let say we have 2 resources. then taking earliest finish time first, we can get two partitions of the intervals as for resource 1: {2,6,8} for resource 2: {1,7} where as if we use earliest start time first, then we will get for resource 1: {1,6,8} for resource 2: {2,5,7} So here the earliest finish time first do not give the optimal result.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.