Question.
There are 5 CPUs and N number of tasks in the queue. You have to use minimum CPUs to process the tasks.
A task is of format [arrival time, time to process the task].
Note:
You can only use at most 5 CPUs. If it is not possible in 5 CPUs, print -1.
The time to process the task should not be greater than 10 i.e (Time waiting in queue + time to process the task) <= 10.
If to process the current task, you need more than 10 seconds in current CPU, you can move to a different CPU and check if it is possible to process the task in <=10 time.
If it is not possible to process the task in <=10 or at most 5 CPUs, print -1.
Constraints.
0 <= Arrival time <= 500
1 <= time to process the task <= 10
0 <= N <=500
You can only use iostream library. No STL's are allowed.
Time : 3 second for T test cases
Eg:-
Input
3
1 6
2 7
3 1
Output
2
Explanation:
3 - N
1 6 - the first task arrives in CPU0 at time 1, and leaves at time 7 (1+6). CPUs used = 1.
2 7 - the second task arrives in CPU0 at time 2, and wait for 5 seconds in the queue, so overall processing time is 5+7 > 10. So it is moved to CPU1. CPUs used = 2.
3 1 - the third task arrives. it can go to CPU0 or CPU1, as processing time is 5
( (7-3) + 1 )and 7( (9-3) + 1 )seconds respectively. CPUs used = 2.CPU1 is a fresh CPU. So task2 will be completed in 9
(2 + 7)seconds without any Time to wait in the queue.
My Approach:
Initially, thought this as a variant of
minimum train-platform problem. But that was wrong.Tried a
greedyapproach, but it gave -1 for some valid solutions.
CODE:
#include <iostream>
using namespace std;
#define MAXN 500
int N;
int arr[MAXN];
int len[MAXN];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>N;
for(int i=0;i<N;i++){
cin>> arr[i] >> len[i];
}
int exit_time_of_task_in_CPUs[5]={0};
int cpus_used_so_far=1;
int min_processing_time;
int min_processing_time_idx;
for(int task_idx=0; task_idx<N; task_idx++){
min_processing_time = INT_MAX;
min_processing_time_idx = -1;
// finds the CPU which can process task in minimum time.
for(int i=0; i<cpus_used_so_far ; i++){
int processing_time = 0;
int time_in_queue = exit_time_of_task_in_CPUs[i] - arr[task_idx];
if( time_in_queue < 0 ) // ie processor is free before arrival
time_in_queue = 0;
processing_time = time_in_queue + len[task_idx];
if( processing_time <=10){
if(processing_time < min_processing_time){
min_processing_time = processing_time;
min_processing_time_idx = i;
}
}
}
if( min_processing_time_idx == -1){
// No Existing CPU can solve this task.
// Check if spawning a new CPU is possible.
if (cpus_used_so_far+1 <= 5){
//spawn a new CPU
cpus_used_so_far++;
int new_cpu_index = cpus_used_so_far - 1; // last CPU, converting to zero index
exit_time_of_task_in_CPUs[new_cpu_index] = arr[task_idx] + len[task_idx] ;
}else{
cpus_used_so_far = -1; // not possible to spawn a new CPU,
break; //and you can't process with existing CPUs
}
}else{
// Possible to handle with existing CPUs
exit_time_of_task_in_CPUs[min_processing_time_idx] = arr[task_idx] + min_processing_time;
}
}
cout << cpus_used_so_far <<endl;
}
- Trying
memoizationapproach.
Recursive approach solves the problem, but it gets timed out. (No wonder)
What is the possible way to save the state of int, int, int[]?
I am also open to an iterative solution for the same.
CODE:
#include <iostream>
using namespace std;
#define MAXN 500
int min_cpus_used = 6;
int N;
int arr[MAXN];
int len[MAXN];
void recurse( int task_idx, int cpus_used_so_far, int exit_time_of_task_in_CPUs[] ){
if( task_idx == N-1){
min_cpus_used = min( min_cpus_used, cpus_used_so_far);
return ;
}
if( cpus_used_so_far >= min_cpus_used ){
return ; //optimization
}
for(int i=0; i<cpus_used_so_far ; i++){
int processing_time = 0;
int time_in_queue = exit_time_of_task_in_CPUs[i] - arr[task_idx];
if( time_in_queue < 0 ) // ie processor is free before arrival
time_in_queue = 0;
processing_time = time_in_queue + len[task_idx];
// try with existing CPUs
if( processing_time <=10){
int prev = exit_time_of_task_in_CPUs[i];
exit_time_of_task_in_CPUs[i] = arr[task_idx] + processing_time;
recurse( task_idx + 1 , cpus_used_so_far , exit_time_of_task_in_CPUs ); // can we optimize passing array
exit_time_of_task_in_CPUs[i] = prev;
}
// try with new CPU
if (cpus_used_so_far+1 <= 5){
int new_cpu_index = cpus_used_so_far + 1 - 1; // converting to zero index
int prev = exit_time_of_task_in_CPUs[new_cpu_index];
exit_time_of_task_in_CPUs[new_cpu_index] = arr[task_idx] + len[task_idx] ;
recurse( task_idx+1 , cpus_used_so_far+1 , exit_time_of_task_in_CPUs );
exit_time_of_task_in_CPUs[new_cpu_index] = prev;
}else{
return ;
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>N;
for(int i=0;i<N;i++){
cin>> arr[i] >> len[i];
}
int exit_time_of_task_in_CPUs[5]={0};
recurse(0, 1, exit_time_of_task_in_CPUs);
if(min_cpus_used==6){
cout<< -1 <<endl;
}else{
cout << min_cpus_used <<endl;
}
}
Kindly help me with your thoughts on optimizing this solution.
PS: This has nothing to do with CPU Scheduling.
