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

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

题目描述

某 Devops 系统有一批并发任务需要匹配合适的执行机调度执行,任务和执行机都具有 CPU 型(用 0 表示)和 IO 型(用 1 表示)的区别,此外还有一种通用型执行机(用 2 表示)。一批任务和执行机的类型分别用数组 tasksmachines 表示,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
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;
}



http://www.kler.cn/a/589983.html

相关文章:

  • 探索具身多模态大模型:开发、数据集和未来方向(下)
  • Node.js系列(1)--架构设计指南
  • Oracle 19c数据库REDO日志更换
  • 深度学习技巧
  • 【位运算】速算密钥:位运算探秘
  • 负载均衡nginx
  • 探索DB-GPT:革新数据库交互的AI原生框架
  • 【数据结构】如何解决二叉树在遍历查找前驱与后继的问题?线索二叉树来帮您……
  • browser_use 自动化浏览器agent使用案例
  • GBase8c 慢SQL配置
  • [CISSP] [2] 安全治理原则策略
  • Python中使用vlc库实现视频播放功能
  • STM32 DAC详解:从原理到实战输出正弦波
  • Description of a Poisson Imagery Super Resolution Algorithm 论文阅读
  • 深入解析网络相关概念​​
  • Unity Webgl在编辑器中报错:Cannot connect to destination host
  • 双模型协作机制的deepseek图片识别
  • Unity组件大全之 Effects特效 |(46)Trail Renderer:绘制动态轨迹的艺术
  • Blender材质 - 层权重
  • 关于微信小程序端base64解码问题