All Tracks Algorithms String Algorithms Problem

Scheduling Algorithm

Algorithms, Binary search algorithm, Hash function, Hashing algorithm, String


You are required to simulate CPU scheduling(assigning processes to CPU in some order for execution) in a newly designed OS. The CPU Scheduling algorithm is as follows: 
There are N ready queues(queues to hold processes waiting for CPU) each with a capacity of L processes.Every ready queue has a unique id from 1 to N and is denoted by RQ[i] where 1<=i<=N. Size of a ready queue denotes the number of elements present in it at some instant and is denoted by S(RQ). Each process(having a priority value from 1 to 50 and lower value meaning higher priority) is thus kept in exactly one ready queue at some position. RQ[i][k] refers to priority of kth process from front in ith ready queue where 1<=k<=S(RQ[i]). A ready queue RQ[i] has more priority than RQ[j] if either of the following is true:

1. S(RQ[i])=S(RQ[j]) and RQ[i][k]=RQ[j][k] for all k where 1<=k<=S(RQ[i]) and i<j

2. S(RQ[i])<S(RQ[j]) and RQ[i][k]=RQ[j][k] for all k where 1<=k<=S(RQ[i]) 
3. RQ[i][t]<RQ[j][t] where 1<=t<=min(S(RQ[i]),S(RQ[j])) and RQ[i][k]=RQ[j][k] for all k where 1<=k<t

The ready queue with the highest priority is selected and its first process is popped and is assigned to CPU. Note that empty ready queues are not compared for priority. The same sequence of steps is repeated until all ready queues are empty.                                
You need to print the priority of the processes in order they will be processed by the CPU for a number of test cases.

Input Format:
The first line contains number of test cases T.
One line containing number of ready queues N and maximum capacity of each ready queue L.      
N lines each consisting of L integers denoting priority of processes in different ready queues.

Output Format: 
A single line consisting of N*L integers denoting priority of processes in order of their execution.

\(1 \le T \le 5\)
\(1 \le N \le 5   \)                                                                                                     
\(1 \le L \le 25000\)

2 3
1 3 1
2 1 50
1 5
50 1 2 48 5
1 2 1 3 1 50
50 1 2 48 5

First test case:
RQ[1]:1 3 1
RQ[2]:2 1 50
1 is popped from RQ[1] as RQ[1] has more priority and 1 is its first element
RQ[1]:3 1
RQ[2]:2 1 50
2 is popped from RQ[2] as RQ[2] has more priority and 2 is its first element.
and so on.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems


This Problem was Asked in

Initializing Code Editor...
View All Notifications