Problem of the day
You are given the ‘N’ processes with their “burst times”, and the “arrival time” for each process is 0.
Your task is to find the “waiting time” and the “turn-around time” of each process using the ‘FCFS CPU Scheduling’ algorithm.
Note:
The process that comes first will be executed first.
Assume all the process has arrived at same time and you have to consider the process with low process id to have arrived first.
The next process starts only after the previous gets fully executed.
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow.
The first line of each test case contains a single positive integer, ‘N’, denoting the number of Processes.
The second line of each test case contains ‘N’ space-separated non-negative integers denoting the ‘burst’ time of each process.
Output Format:
For each test case, print the two lines.
The first will contain the “waiting time” of each process separated by the space in the same order in which they are input.
The second will contain the “turn-around time” of each process separated by the space in the same order in which they are input.
Output for each test case will be printed in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
1 <= T <= 10
1 <= N <= 10^6
1 <= BURST[i], ARRIVAL[i]<= 1000
Where ‘T’ denotes the number of test cases, ‘N’ denotes the number of processes, ‘BURST’ represents the ‘burst time’ of each process, and ‘ARRIVAL’ represents the ‘arrival time’ of each process.
Time Limit: 1sec
1
5
4 6 7 2 1
0 4 10 17 19
4 10 17 19 20
For first test case, as per FCFS algorithm process with get completed line wise. So, 1 process get start at 0 and gets completed at 4 and similarly it goes on till last process. Thus, the waiting time of all process are [ 0, 4, 10, 17, 19] and Finishing time are [ 4, 10, 17, 19, 20].
1
1
3
0
3
For first test case, We have only one process, so it starts at time 0 and ends at time 3.
Try to build an algorithm.
Approach:
Steps:
void findWaitingTime(burstTime, waitingTime):
void findTurnAroundTime(burstTime, waitingTime, turnAroundTime):
O(N), where ‘N’ is the number of processes.
We are considering each process only once and using its values to find the values of other processes. This takes constant time for each process and thus takes O(N) time.
O(N), where ‘N’ is the number of processes.
As we are creating two extra arrays to store the ‘waiting time’ and ‘turn-around time’ of each process, which is of size ‘N’. Hence, space complexity will be O(N).