5 CPU的任务调度N进程 [英] 5 CPU's Task scheduling N process

问题描述

问题。

队列中有5个CPU和N个任务。您必须至少使用
个CPU来处理任务。

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

注意：

1. 您只能在最多5个CPU。如果在5个CPU中不可能，则打印-1。

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

处理任务的时间不应大于10，即（队列中等待的时间+时间来处理任务）< = 10。

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

如果要处理当前任务，则在当前CPU上需要10秒钟以上的时间，则可以移至一个不同的CPU并检查是否有
可以在< = 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.

如果无法处理< = 10或最多5个CPU中的任务，打印-1。

If it is not possible to process the task in <=10 or at most 5 CPUs, print -1.

约束。

0< =到达时间< = 500

0 <= Arrival time <= 500

1< =处理任务的时间< = 10

1 <= time to process the task <= 10

0< = N <= 500

0 <= N <=500

您只能使用iostream库。

You can only use iostream library. No STL's are allowed.

时间：T测试用例需要3秒

Time : 3 second for T test cases

例如：-

输入

Input

3

1 6

2 7

3 1

输出

2

说明：

3-N

3 - N

1 6-第一个任务在时间1到达CPU0，并在时间7（1 + 6）离开。
使用的CPU = 1。

1 6 - the first task arrives in CPU0 at time 1, and leaves at time 7 (1+6). CPUs used = 1.

2 7-第二个任务在时间2到达CPU0，并在队列中等待5
秒，因此总体处理时间为5 + 7>10。因此，将
移至CPU1。使用的CPU = 2。

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-第三项任务到达。它可以转到CPU0或CPU1，因为
的处理时间为5 （（（7-3）+ 1）和7 （（9 -3）+1）秒。使用的CPU = 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是新的CPU。因此task2将在9 （2 + 7）秒内完成，而无需等待队列中的任何时间。

CPU1 is a fresh CPU. So task2 will be completed in 9 (2 + 7) seconds without any Time to wait in the queue.

我的方法：

1. 最初，这被认为是最小火车平台问题的变体。但这是错误的。

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

尝试了贪婪方法，但对于某些有效的解决方案，它给出了-1 。

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

代码：

#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;


}

1. 尝试使用记忆化方法。

1. Trying memoization approach.

递归方法可以解决此问题，但是会超时。 （难怪）

Recursive approach solves the problem, but it gets timed out. (No wonder)

保存 int ，状态的可能方法是什么int ， int [] ？

我也愿意为

代码：

#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：这与CPU调度无关。

PS: This has nothing to do with CPU Scheduling.

推荐答案

摘要：暴力破解答案（最大CPU数），按开始时间对任务进行排序，并使用带有配置文件的DP将该任务按顺序分配给CPU（配置文件是特定对象最近的时刻CPU是可用的；忽略CPU的顺序。

Summary: bruteforce the answer (maximal number of CPUs), sort tasks by start time, assign them to CPUs in that order with DP with profile (profile is the nearest moment when a specific CPU is available; ignore order of CPUs).

该解决方案非常复杂。

The solution is rather sophisticated. Feel free to ask for clarifications.

想法1 ：让我们蛮力地使用最大CPU数并蛮力地使用它（或应用二进制搜索：
如果 A 个CPU足够，那么 A + 1 个CPU也足够）。
现在我们有固定数量的CPU，我们必须解决是/否问题：
是否可以以这种方式安排任务执行？
因为我们最多有5个CPU，所以可以通过一个简单的外部for循环来实现该想法。

Idea 1: let's brute force maximal number of CPUs and brute force it (or apply binary search: if A CPUs are enough, then A+1 CPUs are enough as well). Now we have a fixed number of CPUs and we have to solve a yes/no problem: is it possible to arrange tasks execution in such and such way? AS we have 5 CPUs max, that idea can be implemented with a simple outer for loop.

想法2 ：

证明：采用任何解决方案，选择该条件不成立的最左边的任务，
并注意可以将其向左移动。
减少所有任务的职位总和。
现在，我们选择使价值最小化的解决方案。
它不能有任何在非整数时间开始的任务。

Proof: take any solution, choose the leftmost task for which that condition does not hold, and notice that one can move it further to the left. That reduces total sum of positions of all tasks. Now let's choose the solution which minimizes that value. It cannot have any tasks which start at non-integer times.

想法3 ：有一个满足以下条件的解决方案在每个CPU上：每个尝试任务 A 和 B 的
这样的 A 在 B 之前执行，
A 出现在早于 B 的任务（按到达/创建时间排序）。

Idea 3: there is a solution with the following condition on each CPU: for every try tasks A and B such that A is executed right before B, A occurs in the sorted list of tasks earlier than B (sorted by their arrival/creation time).

证明：采用任意解决方案和冒泡-在每个CPU上排序任务。
我们必须证明交换两个相邻任务不会使解决方案不正确。
考虑任务 A 和 B 这样的任务，使 A 在排序列表中的 B 之后。
这意味着其创建时间不超过 B 的创建时间
，因此 B 在我们开始处理 A 时存在。
这也意味着 A 的期望终止时间不大于 B 的创建时间，
，因此在 B 完成时，我们仍然可以完成 A 。
因此，交换执行顺序不会使解决方案不正确，因此
我们可以自由地这样做。

Proof: take an arbitrary solution and bubble-sort tasks on each CPU. We have to prove that swapping two adjacent tasks does not make the solution incorrect. Consider tasks A and B such that A goes after B in the sorted list. That means that its creation time is not greater than B's creation time, so B exists at the time we started processing A. That also means that A's desired termination time is not greater than B's creation time, so at the time B is completed we're still allowed to complete A. So, swapping their order of execution does not make the solution incorrect and we're free to do so.

想法4 ：可以通过从为所有CPU的空执行
计划开始，然后将任务一个接一个地追加到某些计划，从最早到达的
开始并以最新到达的任务。
我们将任务附加到可以在给定CPU上启动的最短时间内。

Idea 4: it's possible to build a solution by starting with empty execution plans for all CPUs and then appending tasks one-by-one to some plans, starting from the earliest arrived and finished with the latest arrived task. We append task to the lestmost possible time it can be started on a given CPU.

证明：对想法3中的属性采用任意解决方案。 b $ b请注意，每个CPU的执行计划是任务排序列表的子序列。
好​​吧，这意味着可以将排序后的列表中的每个任务分配给一个CPU，
，并且在执行了第4种想法的算法后，我们将得出一些执行计划。
不会比我们原来的解决方案差：所有任务的位置都不会比原始计划中的任务位置大
。
因此，该计划也是解决方案。

Proof: take an arbitrary solution with the property from idea 3. Note that execution plan of each CPU is a subsequence of the sorted list of tasks. Well, that means that each task in the sorted list can be assigned to a CPU, and after performing the algorithm from idea 4 we will end up with some execution plan. It'll be "no worse" than our original solution: positions of all tasks will be not greater than positions of tasks in the original plan. Therefore, that plan is also a solution.

想法5 ：运行递归回溯以查找CPU之间的任务分配。
我们已经知道将它们添加到CPU的顺序（创建顺序）。
跟踪每个CPU上的第一个可用时间，并在搜索的每个步骤中强行分配
进行下一个任务。例如。对于长度为1、5、2、9、3（从零开始）的任务，分配可以是：

Idea 5: run recursive backtracking to find distribution of tasks among CPUs. We already know order in which they should be added to CPUs (the order of creation). Keep track of first available time on each CPU and brute force assignment of the next task on each step of the search. E.g. for tasks of length 1, 5, 2, 9, 3 starting at zero, the assignment may be:

Task start:   0 0 0 0 0
Task length:  1 5 2 9 3
Assigned CPU: A B B A B

想法6 ：添加备忘录（也就是将回溯转换为动态编程）。
请注意，我们并不在意CPU上的第一个可用时间是否少于下一个
任务的开始时间 X ，并且它也不能大于 X + 10 。
因此，每个CPU有11种可能性，即5个CPU的 11 ^ 5 = 161051 可能性
。
这就是我们DP的配置文件。
由于我们不在乎CPU的顺序，因此仅在排列上不同
的配置文件的答案是相同的。
因此，我们只能考虑3003个不同的配置文件（即 \选择{10 + 5} {5} ）。
我们状态中的另一个变量是下一个任务的数量（500种可能性），
，并且每个状态（使用哪个CPU）也有5个转换。
可以进行 3003 * 500 * 5〜8m 的转换，这不是一个很大的数目，因此我们
可以很高兴地将其粉碎在我们的外部区域下-从想法1开始循环。
当然，最好预先计算配置文件之间的转换，但是
也可以不这样做。

Idea 6: add memoization (aka convert backtracking to dynamic programming). Note that we don't really care if first available time on CPU is less than next task's starting time X, and it also can't be greater than X+10. So, we have 11 possibilities for each CPU, that's 11^5=161051 possibilities for 5 CPUs. That's the "profile" of our DP. Since we don't care about order of CPUs, answers for profiles which differ by permutation only are the same. So we can consider 3003 different profiles only (that's \choose{10+5}{5}). Another variable in our state is the number of the next task (500 possibilities), and we also have 5 transitions from each state (which CPU to use). That makes 3003*500*5 ~ 8m transitions, which is not a big number, so we can happily smash it under our outer for-loop from idea 1. Of course, it'd better to precalculate transitions between profiles, but it may also be possible to go without that.

这篇关于5 CPU的任务调度N进程的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！