Answer and Explanation:
single machine scheduling problem where we are given a set T of tasks specified by their start times and finish times
Here we wish to maximise the number of tasks that this machine performs.
We would increase the performance of the machine if we execute more number of task in per unit of time.
To do that if we can follow the SJF(Shortest Job First) Schduling Algorithm, in this algorithm we calculate the burst time of each task.
which is (FT-ST) where FT= Finishing time and ST=Starting Time.
Now if we pick the shortest burst time task first to assign to CPU then we can complete more number of task in per unt of time.
For exa:
Let the Tasks (T1,T2,T3,T4)
Starting Time:(0,3,4,5)
Finishing TIme: (3,4,5,7)
Burst Time:(3,1,1,2)
Therefor if we arrange them in Burst time incresing order (1,1,2,3) = (T2,T3,T4,T1)
We can finish the more number of task in per unit of time.
Running Time:
TO calculate the burst time of n tasks= O(n)
TO arrange the n task in ascending order = O(nlogn)
Therefor Time complexity: (O(n)+O(nlogn)) = O(nlogn)
