the interval scheduling problem and proved that the algorithm described (choosin
ID: 3644474 • Letter: T
Question
the interval scheduling problem and proved that the algorithm described (choosing the interval with earliest deadline) below, always finds an optimal solution. For this problem you will write, analyze, and test several implementations of this algorithm.The following scheduling problem. Imagine you are a highly-in- demand actor, who has been presented with offers to star in n different movie projects under development. Each offer comes specified with the first and last day of filming. To take the job, you must commit to being available throughout this entire period. Thus you cannot simultaneously accept two jobs whose intervals overlap.Must solve the following algorithmic scheduling problem:
Problem: Movie scheduling Problem
Input: A set I of n intervals on the line.
Output: What is the largest subset of the mutually non-overlapping intervals which can selected from I?
Efficient algoritm:
OptimalScheduling (I)
While (I ! = 0) d0
Accept the job from I with the earliest completion date.
Delete j, and any interval, which intersects j from I.
From the interface below implement the algorithm in best way you can think of. Analyze the implementation and give a bound on the execution time. (Hint: it can actually be done in time O(n) plus the cost of sorting the list once.)
public interface IntervalScheduler
{
/**
* Returns a subset of maximal cardinality selected from
* the given list of intervals.
*/
public List<Interval> schedule(List<Interval> intervals);
}