Interval Scheduling
Interval Scheduling
Interval scheduling problem is another problem for process scheduling so that the number of processes we process are maximised. One of the simplest way to solve this problem is by using greedy algorithm.
Greedy Algorithm for Interval Scheduling:
- Pick the earliest finishing process.
- Remove the process which have start time before the end time of the selected process.
- Repeat until there are no process left.
Why does Greedy Algorithm work?
- Suppose there is a process set which is sorted in the order of finish time.
- S = {P0,P1,...,Pn}
- Assume there is a process Pk such that following it may give us more optimal path than using Pk-1.Since, We assumed that Pk-1 finished before Pk. Pk-1 can take all the paths which Pk can take.
In simple terms, If we pick the processes using their sorted end time , it means we can traverse all the paths which a higher indexed process can traverse as it will have its end time greater than or equal to the selected process.
Example:
Let us take the example in which the processes are arranged according to their end time. i.e. end time of P0 will be less than or equal to end time of P1.
We can clearly see the optimal solution is executing 4 processes. We can either pick {P0,P2,P4,P5} or {P0,P3,P4,P5} or {P1,P3,P4,P5} and so on, but at max we would be able to get max set containing 4 processes.
Using greedy algorithm we will:
choose P0, remove P1.
choose P2, remove P3.
choose P4, remove none.
choose P5, remove none.
The reason we get an optimal solution is, If we choose P0, We can go to all the paths which P1 could have traversed, as the end time of P1 would always be greater than or equal to that of process P0. hence by picking the closest end time , we are getting an optimal solution.
