全网最全面的华为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;
}
}
}
相关文章
