Consider the single machine scheduling problem where we are given a set t of tasks specified by their start times and finish times, as in the task scheduling problem, except now we have only one machine and we wish to maximize the number of tasks that this single machine performs. design a greedy algorithm for this single machine scheduling problem and show that it is correct. what is the running time of this algorithm?

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)