2023年华为OD机试真题：任务混部

全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。

真题库：https://www.yuque.com/codernav.com/od

题目：任务混部
题目描述：
公司创新实验室正在研究如何最小化资源成本，最大化资源利用率，请你设计算法帮他们解决一个任务混部问题：有taskNum项任务，每个任务有开始时间（startTime ），结束时间（endTime），并行度(parallelism)三个属性，并行度是指这个任务运行时将会占用的服务器数量，一个服务器在每个时刻可以被任意任务使用但最多被一个任务占用，任务运行完会立即释放（结束时刻不占用）。任务混部问题是指给定一批任务，让这批任务由同一批服务器承载运行，请你计算完成这批任务混部最少需要多少服务器，从而最大化控制资源成本。
输入描述：
第一行输入为taskNum，表示有taskNum项任务
接下来taskNum行，每行三个整数，表示每个任务的开始时间（startTime ），结束时间（endTime），并行度(parallelism)
输出描述：
一个整数，表示最少需要的服务器数量
知识点：差分算法
时间限制：1s 空间限制：256MB 限定语言：不限
补充说明：
1<=taskNum<=100000
0<=startTime<endTime<=50000
1=<parallelism<=100
示例1
输入：
3
2 3 1
6 9 2
0 5 1
输出：
2
说明：
一共有三个任务，第一个任务在时间区间[2,3)运行，占用1个服务器，第二个任务在时间区间[6,9)运行，占用2个服务器，第三个任务在时间区间[0,5)运行，占用1个服务器，需要最多服务器的时间区间为[2,3)和[6,9),需要2个服务器。
示例2
输入：
2
3 9 2
4 7 3
输出：
5
说明：
一共有两个任务，第一个任务在时间区间[3,9)运行，占用2个服务器，第二个任务在时间区间[4,7)运行，占用3个服务器，需要最多服务器的时间区间为[4,7),需要5个服务器。
解题思路：
本题是站长在2023年2月份参加的华为OD机考原题的第3题，用到了差分算法，就是求出所有任务在启动时间时所需要的最大服务器数量。我们可以把题目中涉及到的三个参数封装成类Task，便于后续的操作。
比如示例1中：
3
2 3 1
6 9 2
0 5 1
第一个时间是2：
第一个任务[2，3)，执行中，需要服务器serverCount=1；第二个任务[6，9)，任务不执行；第三个任务[0，5)，任务执行中，需要服务器serverCount=1+1=2；
第二个时间是6：
第一个任务[2，3)，任务不执行；第二个任务[6，9)，执行中，需要服务器serverCount=2；第三个任务[0，5)，任务不执行；需要服务器serverCount=2；
第三个时间是0：
第一个任务[2，3)，任务不执行；第二个任务[6，9)，任务不执行；第三个任务[0，5)，执行中，需要服务器serverCount=1；
综上所述：
serverCount最大值为2，所以输出结果为2。

package com.codernav.demo.hwod.ques;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @title 任务混部
 * @Description 公司创新实验室正在研究如何最小化资源成本，最大化资源利用率，请你设计算法帮他们解决一个任务混部问题：有taskNum项任务，每个任务有开始时间（startTime ），结束时间（endTime），并行度(parallelism)三个属性，并行度是指这个任务运行时将会占用的服务器数量，一个服务器在每个时刻可以被任意任务使用但最多被一个任务占用，任务运行完会立即释放（结束时刻不占用）。任务混部问题是指给定一批任务，让这批任务由同一批服务器承载运行，请你计算完成这批任务混部最少需要多少服务器，从而最大化控制资源成本。
 * @Author 开发者导航
 * @website https://www.codernav.com
 * @date 2023/3/30
 */
public class Main1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int taskNum = sc.nextInt();
        List<Task> tasks = new ArrayList<>();
        for (int i = 0; i < taskNum; i++) {
            Task task = new Task(sc.nextInt(), sc.nextInt(), sc.nextInt());
            tasks.add(task);
        }

        // 每个时间所需要的服务器个数
        int[] serversMap = new int[50000];

        for (Task task : tasks) {
            // startTime：加上所需服务器
            serversMap[task.startTime] += task.parallelism;
            // endTime：减去所需服务器
            serversMap[task.endTime] -= task.parallelism;
        }

        int totalServerNum = 0;
        int result = 0;
        for (int i = 0; i < serversMap.length; i++) {
            // 任务开始加，任务结束减
            totalServerNum += serversMap[i];
            result = Math.max(result, totalServerNum);
        }
        System.out.println(result);
    }

    public static class Task {
        public int startTime;
        public int endTime;
        public int parallelism;

        public Task(int startTime, int endTime, int parallelism) {
            this.startTime = startTime;
            this.endTime = endTime;
            this.parallelism = parallelism;
        }
    }
}