3
\$\begingroup\$

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:

  1. You can only use at most 5 CPUs. If it is not possible in 5 CPUs, print -1.

  2. The time to process the task should not be greater than 10 i.e (Time waiting in queue + time to process the task) <= 10.

  3. 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.

  4. 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:

  1. Initially, thought this as a variant of minimum train-platform problem. But that was wrong.

  2. Tried a greedy approach, but it gave -1 for some valid solutions.

  3. Trying memoization approach.

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.

Below is the 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.

\$\endgroup\$
  • 2
    \$\begingroup\$ We cannot review this because we accept only real code. Pseudocode is off-topic. \$\endgroup\$ – t3chb0t Jun 15 '18 at 8:59
  • 1
    \$\begingroup\$ @t3chb0t I have updated the question with a functional code. Kindly review it. \$\endgroup\$ – Arjun SK Jun 15 '18 at 11:41
  • \$\begingroup\$ See also: 5 CPU's Task scheduling N process over at SO. \$\endgroup\$ – greybeard Jun 17 '18 at 17:21
3
\$\begingroup\$

Read through and bookmark the C++ Standard Guidelines. Numbers I note later are citations from this.

Don’t write using namespace std;.

You can, however, in a CPP file (not H file) or inside a function put individual using std::string; etc. (See SF.7.)


#define MAXN 500

Don't use #define for constants or "functions" (⧺ES.31).


void recurse( int task_idx, int cpus_used_so_far, int  exit_time_of_task_in_CPUs[] ){

That last parameter is a pointer, with the implication that you are passing a pointer to the first of contiguous elements. Don’t pass unknown-sized arrays like that.

(Reading ahead…) since it is of fixed size known at compile time, define it as a std::array instead, both the actual array in main and the parameter (by reference).


int min_cpus_used = 6;

int exit_time_of_task_in_CPUs[5]={0};

if (cpus_used_so_far+1 <= 5){

if(min_cpus_used==6){

Hard-coded magic numbers: are these all related? Define a constant instead of sprinkling these throughout the code.


Let’s see… cpus_used_so_far is not changed within the function, just passed a different value when recursing, right? It would be helpful for readability and analysis to mark it const in the declaration.

    if (cpus_used_so_far+1 <= 5){
            ⋮
    }else{
        return ;
    }

That took me a moment to figure out what the else return was doing at the end of the function just before the closing braces. This would be much clearer if you invert the logic: put the exceptional case first, in the manner of precondition testing.

if (cpus_used_so_far+1 > 5)  return;
⋮

Note that there is no further indenting of the regular code, since it is not nested anymore — it is the main-line of code.


cin.tie(NULL);

Don’t use the C macro NULL. For a null pointer, it is the keyword nullptr.

    cout<< -1 <<endl;

Don’t use endl. Just use \n.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.