当前位置：首页 > article >正文

机试题——Devops 系统任务调度问题

article 2025/3/18 16:39:28

题目描述

某 Devops 系统有一批并发任务需要匹配合适的执行机调度执行，任务和执行机都具有 CPU 型（用 0 表示）和 IO 型（用 1 表示）的区别，此外还有一种通用型执行机（用 2 表示）。一批任务和执行机的类型分别用数组 tasks 和 machines 表示，tasks[i] 表示第 ( i ) 个任务，machines[i] 表示执行机的类型。每台 CPU 型、IO 型执行机只能执行一个对应类型的任务，而通用型执行机既能执行 CPU 类型任务也能执行 IO 类型任务。

假设现有的匹配策略如下：任务需要按照优先级从高到低依次匹配执行机，因此每一轮选择任务数组头部的任务去匹配空置执行机数组头部的执行机，若任务与执行机类型匹配，则代表该任务调度成功，把该执行机从空置执行机数组中移除。若任务与执行机的类型不匹配，则将执行机放到执行机数组尾部，循环该过程直到任务全部匹配成功或当前任务无法被所有剩余空置执行机匹配。

现规定任意时刻都可以选择使用通用执行机，但一旦选择将某个类型的任务匹配通用型执行机，则所有通用型机器都只能用于执行该类型的任务，为了避免任务排队阻塞，请返回现有匹配策略下剩下的最小空置执行机数量。

输入描述

输入共 3 行：

首行是一个正整数 ( n )，表示任务数量以及执行机数量。
第 2 行包含 ( n ) 个整数，以空格分隔，表示为任务数组 tasks。
第 3 行包含 ( n ) 个整数，以空格分隔，表示为空置执行机数组 machines。

数据范围：( 1 < n < 100 )，( 0 < tasks[i] < 1 )，( 0 < machines[i] < 2 )。

输出描述

一行一个整数，代表当前匹配策略下剩下的最小空置执行机数量。

用例输入

3
1 0 1
1 2 0

解题思路

问题分析：

任务和执行机的匹配需要考虑两种情况：直接匹配和使用通用型执行机。
通用型执行机一旦被选择用于某种类型的任务，就不能再用于其他类型的任务。
需要计算两种情况下的最小空置执行机数量：一种是将通用型执行机全部用于 CPU 类型任务，另一种是将通用型执行机全部用于 IO 类型任务。
任务调度过程与执行机的排列顺序无关，因此，我们只需要统计 0 号机和 1 号机的数量，在模拟调度过程中，当机器不足时停止并记录剩余的机器数量。

解题步骤：

计数：统计任务和执行机中每种类型的数量。
模拟匹配：
- 对于每种情况（通用型执行机全部用于 CPU 类型任务或全部用于 IO 类型任务），模拟任务和执行机的匹配过程。
- 在匹配过程中从任务数组头部遍历，匹配任务和执行机的剩余数量。
计算结果：统计每种情况下的剩余空置执行机数量，并返回最小值。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
#include<string>
#include<vector>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<set>
#include<list>
#include<sstream>
#include<bitset>
#include<stack>
#include<climits>
#include<iomanip>
#include<cstdint>
using namespace std;
int n;
//  空置的执行机就是空置的任务数量
int check(vector<int>& tasks, vector<int>& machines) {
    // 直接计数有几个0和1 机器数量是不用考虑顺序的 只考虑计数
    int f0 = 0, f1 = 0;
    for (int i = 0; i < n; i++) {
        if (machines[i]) f1++;
        else f0++;
    }
    for (int i = 0; i < n; i++) {
        if (tasks[i]) {
            if (f1) f1--;
            else return f1 + f0;
        }
        if (!tasks[i]) {
            if(f0) f0--;
            else return f1 + f0;
        }
    }
    return f0 + f1;

    return 0;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    vector<int> tasks(n);
    vector<int> machines(n);
    for (int i = 0; i < n; i++) {
        cin>>tasks[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> machines[i];
    }
    // 全0试下
    vector<int> test0_machines = machines;
    for (int i = 0; i < n; i++) {
        if (test0_machines[i] == 2) test0_machines[i] = 0;
    }
    int res = check(tasks, test0_machines);
    // 全1
    vector<int> test1_machines = machines;
    for (int i = 0; i < n; i++) {
        if (test1_machines[i] == 2) test1_machines[i] = 1;
    }
    res = min(res, check(tasks, test1_machines));
    cout << res;
}