华为OD机试 -任务混部（Java） | 机试题+算法思路+考点+代码解析 【2023】_od任务混部

题目描述：

公司创新实验室正在研究如何最小化资源成本，最大化资源利用率，请你设计算法帮他们解决一个任务混部问题：有taskNum项任务，每个任务有开始时间（startTime ），结束时间（endTime），并行度(parallelism)三个属性，并行度是指这个任务运行时将会占用的服务器数量，一个服务器在每个时刻可以被任意任务使用但最多被一个任务占用，任务运行完会立即释放（结束时刻不占用）。任务混部问题是指给定一批任务，让这批任务由同一批服务器承载运行，请你计算完成这批任务混部最少需要多少服务器，从而最大化控制资源成本。

输入描述：

第一行输入为taskNum，表示有taskNum项任务
接下来taskNum行，每行三个整数，表示每个任务的开始时间（startTime ），结束时间（endTime），并行度(parallelism)

输出描述：

一个整数，表示最少需要的服务器数量

解题思路：

本题用到了差分算法，就是求出所有任务在启动时间时所需要的最大服务器数量。我们可以把题目中涉及到的三个参数封装成类Task，便于后续的操作。
比如：
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 任务混部
 */
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;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51