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

【2024年华为OD机试】 (A卷,200分)- 最大化控制资源成本（JavaScriptJava PythonC/C++）

article 2025/1/27 14:29:45

在这里插入图片描述

一、问题描述

任务混部问题解析

问题描述

公司创新实验室需要解决一个任务混部问题，目标是最小化资源成本并最大化资源利用率。给定一批任务，每个任务有开始时间、结束时间和并行度三个属性。并行度表示任务运行时占用的服务器数量。任务运行完成后立即释放服务器。要求计算完成这批任务混部所需的最少服务器数量。

输入描述

  • 第一行输入为 taskNum，表示任务数量。
  • 接下来 taskNum 行，每行三个整数，分别表示任务的开始时间、结束时间和并行度。

输出描述

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

解题思路

最大区间重叠个数求解

本题的核心思想是求解最大区间重叠个数，但与传统的最大区间重叠问题不同，这里需要考虑每个任务的并行度（权重）。因此，我们需要计算在每个时间点上，所有重叠任务的并行度之和，然后找出最大值。

具体步骤

  1. 事件点生成：

    • 对于每个任务，生成两个事件点：一个是任务开始时间，另一个是任务结束时间。
    • 开始时间的事件点表示任务开始占用服务器，结束时间的事件点表示任务释放服务器。

  2. 事件点排序：

    • 将所有事件点按时间升序排序。如果时间相同，结束事件应优先于开始事件，以确保在任务结束时立即释放服务器。

  3. 遍历事件点：

    • 初始化一个变量 current_servers 来记录当前时间点占用的服务器数量。
    • 初始化一个变量 max_servers 来记录在整个时间轴上占用的最大服务器数量。
    • 遍历排序后的事件点：
      • 如果是开始事件，current_servers 增加该任务的并行度。
      • 如果是结束事件，current_servers 减少该任务的并行度。
      • 每次更新 current_servers 后，检查是否需要更新 max_servers。

  4. 输出结果：

    • 最终 max_servers 即为所需的最少服务器数量。

示例解析

示例 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 个服务器。

总结

通过生成事件点并排序，然后遍历事件点计算每个时间点的服务器占用情况，可以有效地求解任务混部问题。这种方法的时间复杂度为 O(n log n)，适用于大规模任务调度场景。

二、JavaScript算法源码

以下是代码的详细注释和讲解，帮助你理解每一部分的功能和实现逻辑。

代码结构

  1. 输入处理部分：

    • 使用 readline 模块从控制台读取输入。
    • 将输入的任务数据解析为 ranges 数组，每个任务包含 [startTime, endTime, parallelism]。

  2. 核心逻辑部分：

    • 对任务按开始时间排序。
    • 使用优先队列（小顶堆）维护当前正在运行的任务。
    • 遍历任务，动态计算每个时间点的服务器占用总数，并记录最大值。

  3. 优先队列实现：

    • 实现了一个小顶堆（PriorityQueue），用于高效地管理任务的结束时间。

详细注释

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

// 创建 readline 接口
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

// 存储输入的行数据
const lines = [];
let n; // 任务数量

// 监听输入事件
rl.on("line", (line) => {
  lines.push(line); // 将每行输入存入 lines 数组

  // 第一行是任务数量
  if (lines.length === 1) {
    n = lines[0] - 0; // 将字符串转换为数字
  }

  // 当输入行数等于任务数量 + 1 时，表示所有任务数据已输入完毕
  if (n && lines.length === n + 1) {
    // 解析任务数据
    const ranges = lines.slice(1).map((line) => line.split(" ").map(Number));
    // 调用核心逻辑函数并输出结果
    console.log(getResult(ranges));
    // 清空 lines 数组，准备下一次输入
    lines.length = 0;
  }
});

// 核心逻辑函数
function getResult(ranges) {
  // 按任务的开始时间升序排序
  ranges.sort((a, b) => a[0] - b[0]);

  // 创建优先队列（小顶堆），用于存储当前正在运行的任务
  // 堆中存储 [endTime, parallelism]，按 endTime 排序
  const end = new PriorityQueue((a, b) => b[0] - a[0]);

  let max = 0; // 记录最大服务器占用数
  let sum = 0; // 记录当前服务器占用数

  // 遍历所有任务
  for (let range of ranges) {
    const [s, e, p] = range; // 解构任务属性：开始时间、结束时间、并行度

    // 弹出所有已结束的任务
    while (end.size()) {
      const top = end.peek(); // 查看堆顶任务

      // 如果堆顶任务的结束时间 <= 当前任务的开始时间，说明该任务已结束
      if (top[0] <= s) {
        const poll = end.shift(); // 弹出堆顶任务
        sum -= poll[1]; // 减少当前服务器占用数
      } else {
        break; // 如果堆顶任务未结束，停止弹出
      }
    }

    // 将当前任务加入堆
    end.push([e, p]);
    sum += p; // 增加当前服务器占用数

    // 更新最大服务器占用数
    if (sum > max) {
      max = sum;
    }
  }

  // 返回最大服务器占用数
  return max;
}

// 优先队列（小顶堆）实现
class PriorityQueue {
  constructor(cpr) {
    this.queue = []; // 存储堆的数组
    this.cpr = cpr; // 比较函数，用于确定堆的顺序
  }

  // 交换堆中两个元素
  swap(a, b) {
    const tmp = this.queue[a];
    this.queue[a] = this.queue[b];
    this.queue[b] = tmp;
  }

  // 上浮操作：将新插入的元素调整到正确位置
  swim() {
    let c = this.queue.length - 1; // 当前节点索引

    while (c >= 1) {
      const f = Math.floor((c - 1) / 2); // 父节点索引

      // 如果当前节点比父节点小，交换位置
      if (this.cpr(this.queue[c], this.queue[f]) > 0) {
        this.swap(c, f);
        c = f; // 继续向上调整
      } else {
        break; // 如果当前节点已满足堆性质，停止调整
      }
    }
  }

  // 入队操作：将元素插入堆
  push(val) {
    this.queue.push(val); // 将元素插入堆尾
    this.swim(); // 上浮调整
  }

  // 下沉操作：将堆顶元素调整到正确位置
  sink() {
    let f = 0; // 当前节点索引

    while (true) {
      let c1 = 2 * f + 1; // 左子节点索引
      let c2 = c1 + 1; // 右子节点索引

      let c; // 需要交换的子节点索引
      let val1 = this.queue[c1]; // 左子节点值
      let val2 = this.queue[c2]; // 右子节点值

      // 选择较小的子节点
      if (val1 && val2) {
        c = this.cpr(val1, val2) > 0 ? c1 : c2;
      } else if (val1 && !val2) {
        c = c1;
      } else if (!val1 && val2) {
        c = c2;
      } else {
        break; // 如果没有子节点，停止调整
      }

      // 如果当前节点比子节点大，交换位置
      if (this.cpr(this.queue[c], this.queue[f]) > 0) {
        this.swap(c, f);
        f = c; // 继续向下调整
      } else {
        break; // 如果当前节点已满足堆性质，停止调整
      }
    }
  }

  // 出队操作：弹出堆顶元素
  shift() {
    this.swap(0, this.queue.length - 1); // 将堆顶元素与堆尾元素交换
    const res = this.queue.pop(); // 弹出堆尾元素
    this.sink(); // 下沉调整
    return res; // 返回堆顶元素
  }

  // 查看堆顶元素
  peek() {
    return this.queue[0];
  }

  // 返回堆的大小
  size() {
    return this.queue.length;
  }
}

代码讲解

1. 输入处理
  • 使用 readline 模块逐行读取输入。
  • 第一行是任务数量 n，后续 n 行是每个任务的 [startTime, endTime, parallelism]。
  • 将任务数据解析为 ranges 数组。
2. 核心逻辑
  • 排序：将任务按开始时间升序排序，确保按时间顺序处理任务。
  • 优先队列：使用小顶堆维护当前正在运行的任务。堆中存储 [endTime, parallelism]，按 endTime 排序。
  • 遍历任务：
    • 对于每个任务，弹出所有已结束的任务（endTime <= 当前任务开始时间），并减少当前服务器占用数。
    • 将当前任务加入堆，并增加当前服务器占用数。
    • 更新最大服务器占用数。
3. 优先队列实现
  • 上浮（swim）：将新插入的元素调整到正确位置，保持堆的性质。
  • 下沉（sink）：将堆顶元素调整到正确位置，保持堆的性质。
  • 入队（push）：将元素插入堆尾，并上浮调整。
  • 出队（shift）：弹出堆顶元素，并下沉调整。
  • 查看堆顶（peek）：返回堆顶元素。
  • 堆大小（size）：返回堆中元素数量。

总结

  • 该代码通过排序和优先队列，高效地计算了任务混部所需的最少服务器数量。
  • 优先队列的实现确保了任务结束时间的动态管理，时间复杂度为 O(n log n)，适用于大规模任务调度场景。

三、Java算法源码

以下是代码的详细注释和讲解，帮助你理解每一部分的功能和实现逻辑。

代码结构

  1. 输入处理部分：

    • 使用 Scanner 从控制台读取输入。
    • 将输入的任务数据解析为 ranges 数组，每个任务包含 [startTime, endTime, parallelism]。

  2. 核心逻辑部分：

    • 对任务按开始时间排序。
    • 使用优先队列（小顶堆）维护当前正在运行的任务。
    • 遍历任务，动态计算每个时间点的服务器占用总数，并记录最大值。

  3. 优先队列使用：

    • 使用 Java 的 PriorityQueue 实现小顶堆，用于高效地管理任务的结束时间。

详细注释

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    // 创建 Scanner 对象，用于读取输入
    Scanner sc = new Scanner(System.in);

    // 读取任务数量
    int n = sc.nextInt();

    // 定义 ranges 数组，存储每个任务的 [startTime, endTime, parallelism]
    int[][] ranges = new int[n][3];

    // 读取每个任务的属性
    for (int i = 0; i < n; i++) {
      ranges[i][0] = sc.nextInt(); // 开始时间
      ranges[i][1] = sc.nextInt(); // 结束时间
      ranges[i][2] = sc.nextInt(); // 并行度
    }

    // 调用核心逻辑函数并输出结果
    System.out.println(getResult(ranges));
  }

  // 核心逻辑函数
  public static int getResult(int[][] ranges) {
    // 按任务的开始时间升序排序
    Arrays.sort(ranges, (a, b) -> a[0] - b[0]);

    // 创建优先队列（小顶堆），用于存储当前正在运行的任务
    // 堆中存储 [endTime, parallelism]，按 endTime 排序
    PriorityQueue<Integer[]> end = new PriorityQueue<>((a, b) -> a[0] - b[0]);

    int max = 0; // 记录最大服务器占用数
    int sum = 0; // 记录当前服务器占用数

    // 遍历所有任务
    for (int[] range : ranges) {
      int s = range[0]; // 当前任务的开始时间
      int e = range[1]; // 当前任务的结束时间
      int p = range[2]; // 当前任务的并行度

      // 弹出所有已结束的任务
      while (end.size() > 0) {
        Integer[] top = end.peek(); // 查看堆顶任务

        // 如果堆顶任务的结束时间 <= 当前任务的开始时间，说明该任务已结束
        if (top[0] <= s) {
          Integer[] poll = end.poll(); // 弹出堆顶任务
          sum -= poll[1]; // 减少当前服务器占用数
        } else {
          break; // 如果堆顶任务未结束，停止弹出
        }
      }

      // 将当前任务加入堆
      end.offer(new Integer[] {e, p});
      sum += p; // 增加当前服务器占用数

      // 更新最大服务器占用数
      if (sum > max) {
        max = sum;
      }
    }

    // 返回最大服务器占用数
    return max;
  }
}

代码讲解

1. 输入处理
  • 使用 Scanner 从控制台读取输入。
  • 第一行是任务数量 n，后续 n 行是每个任务的 [startTime, endTime, parallelism]。
  • 将任务数据解析为 ranges 数组。
2. 核心逻辑
  • 排序：将任务按开始时间升序排序，确保按时间顺序处理任务。
  • 优先队列：使用 PriorityQueue 实现小顶堆，堆中存储 [endTime, parallelism]，按 endTime 排序。
  • 遍历任务：
    • 对于每个任务，弹出所有已结束的任务（endTime <= 当前任务开始时间），并减少当前服务器占用数。
    • 将当前任务加入堆，并增加当前服务器占用数。
    • 更新最大服务器占用数。
3. 优先队列使用
  • PriorityQueue：Java 提供的优先队列实现，默认是小顶堆。
  • offer：将元素插入堆。
  • poll：弹出堆顶元素。
  • peek：查看堆顶元素。

示例运行

输入 1
3
2 3 1
6 9 2
0 5 1
输出 1
2
解释
  • 任务 1：[2, 3]，占用 1 个服务器。
  • 任务 2：[6, 9]，占用 2 个服务器。
  • 任务 3：[0, 5]，占用 1 个服务器。
  • 最大服务器占用数为 2（时间区间 [2, 3] 和 [6, 9]）。
输入 2
2
3 9 2
4 7 3
输出 2
5
解释
  • 任务 1：[3, 9]，占用 2 个服务器。
  • 任务 2：[4, 7]，占用 3 个服务器。
  • 最大服务器占用数为 5（时间区间 [4, 7]）。

总结

  • 该代码通过排序和优先队列，高效地计算了任务混部所需的最少服务器数量。
  • 优先队列的使用确保了任务结束时间的动态管理，时间复杂度为 O(n log n)，适用于大规模任务调度场景。

四、Python算法源码

以下是代码的详细注释和讲解，帮助你理解每一部分的功能和实现逻辑。

代码结构

  1. 输入处理部分：

    • 使用 input() 从控制台读取输入。
    • 将输入的任务数据解析为 ranges 列表，每个任务包含 [startTime, endTime, parallelism]。

  2. 核心逻辑部分：

    • 对任务按开始时间排序。
    • 使用优先队列（小顶堆）维护当前正在运行的任务。
    • 遍历任务，动态计算每个时间点的服务器占用总数，并记录最大值。

  3. 优先队列使用：

    • 使用 Python 的 queue.PriorityQueue 实现小顶堆，用于高效地管理任务的结束时间。

详细注释

import queue

# 输入获取
taskNum = int(input())  # 读取任务数量
ranges = [list(map(int, input().split())) for i in range(taskNum)]  # 读取每个任务的属性

# 算法入口
def getResult(ranges):
    # 按任务的开始时间升序排序
    ranges.sort(key=lambda x: x[0])

    # 创建优先队列（小顶堆），用于存储当前正在运行的任务
    # 堆中存储 (endTime, parallelism)，按 endTime 排序
    end = queue.PriorityQueue()

    maxV = 0  # 记录最大服务器占用数
    sum = 0  # 记录当前服务器占用数

    # 遍历所有任务
    for ran in ranges:
        s, e, p = ran  # 解构任务属性：开始时间、结束时间、并行度

        # 弹出所有已结束的任务
        while end.qsize() > 0:
            top = end.queue[0]  # 查看堆顶任务

            # 如果堆顶任务的结束时间 <= 当前任务的开始时间，说明该任务已结束
            if top[0] <= s:
                poll = end.get()  # 弹出堆顶任务
                sum -= poll[1]  # 减少当前服务器占用数
            else:
                break  # 如果堆顶任务未结束，停止弹出

        # 将当前任务加入堆
        end.put((e, p))
        sum += p  # 增加当前服务器占用数

        # 更新最大服务器占用数
        if sum > maxV:
            maxV = sum

    # 返回最大服务器占用数
    return maxV

# 算法调用
print(getResult(ranges))

代码讲解

1. 输入处理
  • 使用 input() 从控制台读取输入。
  • 第一行是任务数量 taskNum，后续 taskNum 行是每个任务的 [startTime, endTime, parallelism]。
  • 将任务数据解析为 ranges 列表。
2. 核心逻辑
  • 排序：将任务按开始时间升序排序，确保按时间顺序处理任务。
  • 优先队列：使用 queue.PriorityQueue 实现小顶堆，堆中存储 (endTime, parallelism)，按 endTime 排序。
  • 遍历任务：
    • 对于每个任务，弹出所有已结束的任务（endTime <= 当前任务开始时间），并减少当前服务器占用数。
    • 将当前任务加入堆，并增加当前服务器占用数。
    • 更新最大服务器占用数。
3. 优先队列使用
  • PriorityQueue：Python 提供的优先队列实现，默认是小顶堆。
  • put：将元素插入堆。
  • get：弹出堆顶元素。
  • queue[0]：查看堆顶元素（通过直接访问内部列表）。

示例运行

输入 1
3
2 3 1
6 9 2
0 5 1
输出 1
2
解释
  • 任务 1：[2, 3]，占用 1 个服务器。
  • 任务 2：[6, 9]，占用 2 个服务器。
  • 任务 3：[0, 5]，占用 1 个服务器。
  • 最大服务器占用数为 2（时间区间 [2, 3] 和 [6, 9]）。
输入 2
2
3 9 2
4 7 3
输出 2
5
解释
  • 任务 1：[3, 9]，占用 2 个服务器。
  • 任务 2：[4, 7]，占用 3 个服务器。
  • 最大服务器占用数为 5（时间区间 [4, 7]）。

总结

  • 该代码通过排序和优先队列，高效地计算了任务混部所需的最少服务器数量。
  • 优先队列的使用确保了任务结束时间的动态管理，时间复杂度为 O(n log n)，适用于大规模任务调度场景。

五、C/C++算法源码：

以下是 C++ 和 C语言 版本的代码实现，附带详细的中文注释和代码讲解。

C++ 版本

代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

// 核心逻辑函数
int getResult(vector<vector<int>>& ranges) {
    // 按任务的开始时间升序排序
    sort(ranges.begin(), ranges.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    });

    // 创建优先队列（小顶堆），用于存储当前正在运行的任务
    // 堆中存储 {endTime, parallelism}，按 endTime 排序
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> end;

    int maxV = 0; // 记录最大服务器占用数
    int sum = 0;  // 记录当前服务器占用数

    // 遍历所有任务
    for (const auto& ran : ranges) {
        int s = ran[0]; // 当前任务的开始时间
        int e = ran[1]; // 当前任务的结束时间
        int p = ran[2]; // 当前任务的并行度

        // 弹出所有已结束的任务
        while (!end.empty()) {
            auto top = end.top(); // 查看堆顶任务

            // 如果堆顶任务的结束时间 <= 当前任务的开始时间，说明该任务已结束
            if (top.first <= s) {
                sum -= top.second; // 减少当前服务器占用数
                end.pop();         // 弹出堆顶任务
            } else {
                break; // 如果堆顶任务未结束，停止弹出
            }
        }

        // 将当前任务加入堆
        end.push({e, p});
        sum += p; // 增加当前服务器占用数

        // 更新最大服务器占用数
        if (sum > maxV) {
            maxV = sum;
        }
    }

    return maxV;
}

int main() {
    int taskNum;
    cin >> taskNum; // 读取任务数量

    vector<vector<int>> ranges(taskNum, vector<int>(3));
    for (int i = 0; i < taskNum; i++) {
        cin >> ranges[i][0] >> ranges[i][1] >> ranges[i][2]; // 读取每个任务的属性
    }

    // 调用核心逻辑函数并输出结果
    cout << getResult(ranges) << endl;
    return 0;
}

C++ 代码讲解

  1. 输入处理：

    • 使用 cin 从控制台读取输入。
    • 第一行是任务数量 taskNum，后续 taskNum 行是每个任务的 [startTime, endTime, parallelism]。
    • 将任务数据解析为 ranges 向量。

  2. 核心逻辑：

    • 排序：使用 sort 函数按任务的开始时间升序排序。
    • 优先队列：使用 priority_queue 实现小顶堆，堆中存储 {endTime, parallelism}，按 endTime 排序。
    • 遍历任务：
      • 对于每个任务，弹出所有已结束的任务（endTime <= 当前任务开始时间），并减少当前服务器占用数。
      • 将当前任务加入堆，并增加当前服务器占用数。
      • 更新最大服务器占用数。

  3. 优先队列使用：

    • priority_queue：C++ 提供的优先队列实现，默认是大顶堆，通过 greater 实现小顶堆。
    • push：将元素插入堆。
    • pop：弹出堆顶元素。
    • top：查看堆顶元素。

C语言版本

代码实现

#include <stdio.h>
#include <stdlib.h>

// 定义任务结构体
typedef struct {
    int startTime;
    int endTime;
    int parallelism;
} Task;

// 定义堆节点结构体
typedef struct {
    int endTime;
    int parallelism;
} HeapNode;

// 堆的实现
HeapNode heap[100001]; // 堆数组
int heapSize = 0;      // 堆大小

// 上浮操作
void swim(int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (heap[index].endTime < heap[parent].endTime) {
            // 交换当前节点和父节点
            HeapNode temp = heap[index];
            heap[index] = heap[parent];
            heap[parent] = temp;
            index = parent;
        } else {
            break;
        }
    }
}

// 下沉操作
void sink(int index) {
    while (2 * index + 1 < heapSize) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int min = left;

        if (right < heapSize && heap[right].endTime < heap[left].endTime) {
            min = right;
        }

        if (heap[index].endTime > heap[min].endTime) {
            // 交换当前节点和最小子节点
            HeapNode temp = heap[index];
            heap[index] = heap[min];
            heap[min] = temp;
            index = min;
        } else {
            break;
        }
    }
}

// 插入堆
void push(int endTime, int parallelism) {
    heap[heapSize].endTime = endTime;
    heap[heapSize].parallelism = parallelism;
    swim(heapSize);
    heapSize++;
}

// 弹出堆顶元素
HeapNode pop() {
    HeapNode top = heap[0];
    heap[0] = heap[heapSize - 1];
    heapSize--;
    sink(0);
    return top;
}

// 查看堆顶元素
HeapNode peek() {
    return heap[0];
}

// 比较函数，用于排序
int compare(const void* a, const void* b) {
    Task* taskA = (Task*)a;
    Task* taskB = (Task*)b;
    return taskA->startTime - taskB->startTime;
}

// 核心逻辑函数
int getResult(Task* tasks, int taskNum) {
    // 按任务的开始时间升序排序
    qsort(tasks, taskNum, sizeof(Task), compare);

    int maxV = 0; // 记录最大服务器占用数
    int sum = 0;  // 记录当前服务器占用数

    // 遍历所有任务
    for (int i = 0; i < taskNum; i++) {
        int s = tasks[i].startTime;
        int e = tasks[i].endTime;
        int p = tasks[i].parallelism;

        // 弹出所有已结束的任务
        while (heapSize > 0) {
            HeapNode top = peek();
            if (top.endTime <= s) {
                HeapNode poll = pop();
                sum -= poll.parallelism;
            } else {
                break;
            }
        }

        // 将当前任务加入堆
        push(e, p);
        sum += p;

        // 更新最大服务器占用数
        if (sum > maxV) {
            maxV = sum;
        }
    }

    return maxV;
}

int main() {
    int taskNum;
    scanf("%d", &taskNum); // 读取任务数量

    Task* tasks = (Task*)malloc(taskNum * sizeof(Task));
    for (int i = 0; i < taskNum; i++) {
        scanf("%d %d %d", &tasks[i].startTime, &tasks[i].endTime, &tasks[i].parallelism);
    }

    // 调用核心逻辑函数并输出结果
    printf("%d\n", getResult(tasks, taskNum));

    free(tasks);
    return 0;
}

C语言代码讲解

  1. 输入处理：

    • 使用 scanf 从控制台读取输入。
    • 第一行是任务数量 taskNum，后续 taskNum 行是每个任务的 [startTime, endTime, parallelism]。
    • 将任务数据解析为 tasks 数组。

  2. 核心逻辑：

    • 排序：使用 qsort 函数按任务的开始时间升序排序。
    • 堆的实现：手动实现小顶堆，包括 swim（上浮）和 sink（下沉）操作。
    • 遍历任务：
      • 对于每个任务，弹出所有已结束的任务（endTime <= 当前任务开始时间），并减少当前服务器占用数。
      • 将当前任务加入堆，并增加当前服务器占用数。
      • 更新最大服务器占用数。

  3. 堆的实现：

    • push：将元素插入堆。
    • pop：弹出堆顶元素。
    • peek：查看堆顶元素。

总结

  • C++ 版本：利用 STL 的 priority_queue 实现优先队列，代码简洁高效。
  • C语言版本：手动实现小顶堆，适合对底层数据结构有深入理解的学习者。
  • 两种版本的时间复杂度均为 O(n log n)，适用于大规模任务调度场景。

差分数列求解

以下是 Java、JavaScript 和 Python 版本的代码实现，附带详细的中文注释和代码讲解。

Java 版本

代码实现

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    // 读取任务数量
    int n = sc.nextInt();

    // 定义 ranges 数组，存储每个任务的 [startTime, endTime, parallelism]
    int[][] ranges = new int[n][3];

    // 读取每个任务的属性
    for (int i = 0; i < n; i++) {
      ranges[i][0] = sc.nextInt(); // 开始时间
      ranges[i][1] = sc.nextInt(); // 结束时间
      ranges[i][2] = sc.nextInt(); // 并行度
    }

    // 调用核心逻辑函数并输出结果
    System.out.println(getResult(ranges));
  }

  // 核心逻辑函数
  public static int getResult(int[][] ranges) {
    // 定义差分数列，初始化为 0
    int[] arr = new int[50000];

    // 遍历所有任务
    for (int[] range : ranges) {
      int start = range[0]; // 当前任务的开始时间
      int end = range[1];   // 当前任务的结束时间
      int diff = range[2];  // 当前任务的并行度

      // 在差分数列的 start 位置增加 diff
      arr[start] += diff;
      // 在差分数列的 end 位置减少 diff
      // 注意：结束时刻不占用服务器，因此不需要 end + 1
      arr[end] -= diff;
    }

    // 初始化最大服务器占用数为差分数列的第一个元素
    int ans = arr[0];

    // 求解差分数列的前缀和
    for (int i = 1; i < arr.length; i++) {
      arr[i] += arr[i - 1]; // 计算前缀和
      ans = Math.max(ans, arr[i]); // 更新最大服务器占用数
    }

    // 返回最大服务器占用数
    return ans;
  }
}

Java 代码讲解

  1. 输入处理：

    • 使用 Scanner 从控制台读取输入。
    • 第一行是任务数量 n，后续 n 行是每个任务的 [startTime, endTime, parallelism]。
    • 将任务数据解析为 ranges 数组。

  2. 核心逻辑：

    • 差分数列：
      • 初始化一个长度为 50000 的数组 arr，用于存储差分数列。
      • 对于每个任务，在 start 位置增加 diff，在 end 位置减少 diff。
    • 前缀和计算：
      • 遍历差分数列，计算前缀和，得到每个时间点的服务器占用数。
      • 更新最大服务器占用数 ans。

  3. 输出结果：

    • 返回最大服务器占用数 ans。

JavaScript 版本

代码实现

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
let n;

// 监听输入事件
rl.on("line", (line) => {
  lines.push(line);

  // 第一行是任务数量
  if (lines.length === 1) {
    n = lines[0] - 0;
  }

  // 当输入行数等于任务数量 + 1 时，表示所有任务数据已输入完毕
  if (n && lines.length === n + 1) {
    // 解析任务数据
    const ranges = lines.slice(1).map((line) => line.split(" ").map(Number));
    // 调用核心逻辑函数并输出结果
    console.log(getResult(ranges));
    // 清空 lines 数组，准备下一次输入
    lines.length = 0;
  }
});

// 核心逻辑函数
function getResult(ranges) {
  // 定义差分数列，初始化为 0
  const arr = new Array(50000).fill(0);

  // 遍历所有任务
  for (let [start, end, diff] of ranges) {
    // 在差分数列的 start 位置增加 diff
    arr[start] += diff;
    // 在差分数列的 end 位置减少 diff
    // 注意：结束时刻不占用服务器，因此不需要 end + 1
    arr[end] -= diff;
  }

  // 初始化最大服务器占用数为差分数列的第一个元素
  let ans = arr[0];

  // 求解差分数列的前缀和
  for (let i = 1; i < arr.length; i++) {
    arr[i] += arr[i - 1]; // 计算前缀和
    ans = Math.max(ans, arr[i]); // 更新最大服务器占用数
  }

  // 返回最大服务器占用数
  return ans;
}

JavaScript 代码讲解

  1. 输入处理：

    • 使用 readline 模块从控制台读取输入。
    • 第一行是任务数量 n，后续 n 行是每个任务的 [startTime, endTime, parallelism]。
    • 将任务数据解析为 ranges 数组。

  2. 核心逻辑：

    • 差分数列：
      • 初始化一个长度为 50000 的数组 arr，用于存储差分数列。
      • 对于每个任务，在 start 位置增加 diff，在 end 位置减少 diff。
    • 前缀和计算：
      • 遍历差分数列，计算前缀和，得到每个时间点的服务器占用数。
      • 更新最大服务器占用数 ans。

  3. 输出结果：

    • 返回最大服务器占用数 ans。

Python 版本

代码实现

# 输入获取
taskNum = int(input())
ranges = [list(map(int, input().split())) for i in range(taskNum)]

# 算法入口
def getResult(ranges):
    # 定义差分数列，初始化为 0
    arr = [0] * 50000

    # 遍历所有任务
    for start, end, diff in ranges:
        # 在差分数列的 start 位置增加 diff
        arr[start] += diff
        # 在差分数列的 end 位置减少 diff
        # 注意：结束时刻不占用服务器，因此不需要 end + 1
        arr[end] -= diff

    # 初始化最大服务器占用数为差分数列的第一个元素
    ans = arr[0]

    # 求解差分数列的前缀和
    for i in range(1, 50000):
        arr[i] += arr[i - 1]  # 计算前缀和
        ans = max(ans, arr[i])  # 更新最大服务器占用数

    # 返回最大服务器占用数
    return ans

# 算法调用
print(getResult(ranges))

Python 代码讲解

  1. 输入处理：

    • 使用 input() 从控制台读取输入。
    • 第一行是任务数量 taskNum，后续 taskNum 行是每个任务的 [startTime, endTime, parallelism]。
    • 将任务数据解析为 ranges 列表。

  2. 核心逻辑：

    • 差分数列：
      • 初始化一个长度为 50000 的列表 arr，用于存储差分数列。
      • 对于每个任务，在 start 位置增加 diff，在 end 位置减少 diff。
    • 前缀和计算：
      • 遍历差分数列，计算前缀和，得到每个时间点的服务器占用数。
      • 更新最大服务器占用数 ans。

  3. 输出结果：

    • 返回最大服务器占用数 ans。

总结

  • 差分数列：通过差分数列高效处理区间增量问题。
  • 前缀和计算：通过前缀和还原每个时间点的服务器占用数。
  • 时间复杂度：O(n + m)，其中 n 是任务数量，m 是时间范围（50000）。
  • 空间复杂度：O(m)，用于存储差分数列。

六、尾言

什么是华为OD？

华为OD（Outsourcing Developer，外包开发工程师）是华为针对软件开发工程师岗位的一种招聘形式，主要包括笔试、技术面试以及综合面试等环节。尤其在笔试部分，算法题的机试至关重要。

为什么刷题很重要？

  1. 机试是进入技术面的第一关：
    华为OD机试（常被称为机考）主要考察算法和编程能力。只有通过机试，才能进入后续的技术面试环节。

  2. 技术面试需要手撕代码：
    技术一面和二面通常会涉及现场编写代码或算法题。面试官会注重考察候选人的思路清晰度、代码规范性以及解决问题的能力。因此提前刷题、多练习是通过面试的重要保障。

  3. 入职后的可信考试：
    入职华为后，还需要通过“可信考试”。可信考试分为三个等级：

    • 入门级：主要考察基础算法与编程能力。
    • 工作级：更贴近实际业务需求，可能涉及复杂的算法或与工作内容相关的场景题目。
    • 专业级：最高等级，考察深层次的算法以及优化能力，与薪资直接挂钩。

刷题策略与说明：

2024年8月14日之后，华为OD机试的题库转为 E卷，由往年题库（D卷、A卷、B卷、C卷）和全新题目组成。刷题时可以参考以下策略：

  1. 关注历年真题：

    • 题库中的旧题占比较大，建议优先刷历年的A卷、B卷、C卷、D卷题目。
    • 对于每道题目，建议深度理解其解题思路、代码实现，以及相关算法的适用场景。

  2. 适应新题目：

    • E卷中包含全新题目，需要掌握全面的算法知识和一定的灵活应对能力。
    • 建议关注新的刷题平台或交流群，获取最新题目的解析和动态。

  3. 掌握常见算法：
    华为OD考试通常涉及以下算法和数据结构：

    • 排序算法（快速排序、归并排序等）
    • 动态规划（背包问题、最长公共子序列等）
    • 贪心算法
    • 栈、队列、链表的操作
    • 图论（最短路径、最小生成树等）
    • 滑动窗口、双指针算法

  4. 保持编程规范：

    • 注重代码的可读性和注释的清晰度。
    • 熟练使用常见编程语言，如C++、Java、Python等。

如何获取资源？

  1. 官方参考：

    • 华为招聘官网或相关的招聘平台会有一些参考信息。
    • 华为OD的相关公众号可能也会发布相关的刷题资料或学习资源。

  2. 加入刷题社区：

    • 找到可信的刷题交流群，与其他备考的小伙伴交流经验。
    • 关注知名的刷题网站，如LeetCode、牛客网等，这些平台上有许多华为OD的历年真题和解析。

  3. 寻找系统性的教程：

    • 学习一本经典的算法书籍，例如《算法导论》《剑指Offer》《编程之美》等。
    • 完成系统的学习课程，例如数据结构与算法的在线课程。

积极心态与持续努力：

刷题的过程可能会比较枯燥，但它能够显著提升编程能力和算法思维。无论是为了通过华为OD的招聘考试，还是为了未来的职业发展，这些积累都会成为重要的财富。

考试注意细节

  1. 本地编写代码

    • 在本地 IDE（如 VS Code、PyCharm 等）上编写、保存和调试代码，确保逻辑正确后再复制粘贴到考试页面。这样可以减少语法错误，提高代码准确性。

  2. 调整心态，保持冷静

    • 遇到提示不足或实现不确定的问题时，不必慌张，可以采用更简单或更有把握的方法替代，确保思路清晰。

  3. 输入输出完整性

    • 注意训练和考试时都需要编写完整的输入输出代码，尤其是和题目示例保持一致。完成代码后务必及时调试，确保功能符合要求。

  4. 快捷键使用

    • 删除行可用 Ctrl+D，复制、粘贴和撤销分别为 Ctrl+C，Ctrl+V，Ctrl+Z，这些可以正常使用。
    • 避免使用 Ctrl+S，以免触发浏览器的保存功能。

  5. 浏览器要求

    • 使用最新版的 Google Chrome 浏览器完成考试，确保摄像头开启并正常工作。考试期间不要切换到其他网站，以免影响考试成绩。

  6. 交卷相关

    • 答题前，务必仔细查看题目示例，避免遗漏要求。
    • 每完成一道题后，点击【保存并调试】按钮，多次保存和调试是允许的，系统会记录得分最高的一次结果。完成所有题目后，点击【提交本题型】按钮。
    • 确保在考试结束前提交试卷，避免因未保存或调试失误而丢分。

  7. 时间和分数安排

    • 总时间：150 分钟；总分：400 分。
    • 试卷结构：2 道一星难度题（每题 100 分），1 道二星难度题（200 分）。及格分为 150 分。合理分配时间，优先完成自己擅长的题目。

  8. 考试环境准备

    • 考试前请备好草稿纸和笔。考试中尽量避免离开座位，确保监控画面正常。
    • 如需上厕所，请提前规划好时间以减少中途离开监控的可能性。

  9. 技术问题处理

    • 如果考试中遇到断电、断网、死机等技术问题，可以关闭浏览器并重新打开试卷链接继续作答。
    • 出现其他问题，请第一时间联系 HR 或监考人员进行反馈。

祝你考试顺利，取得理想成绩！


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

相关文章：

  • CAN总线
  • PyTorch中的movedim、transpose与permute
  • Spring Boot是什么及其优点
  • 双足机器人开源项目
  • Golang Gin系列-9：Gin 集成Swagger生成文档
  • 在小红书挖掘信息的实践之旅（第一部分）
  • 正则表达式 - 命名捕获组
  • 【C语言学习】：C语言补充：转义字符，＜＜,＞＞操作符，IDE
  • 9.中断系统、EXTI外部中断
  • 软件开发中的密码学（国密算法）
  • 1_相向双指针_leetcode_167_1
  • UE学习日志#11GAS--ASC源码简要分析9 AbilitySystemGlobals分析2 初始化相关
  • Chapter 3-17. Detecting Congestion in Fibre Channel Fabrics
  • Java多线程与高并发专题——保障原子性
  • 【FreeRTOS 教程 五】FreeRTOS 内存管理细致讲解
  • easyexcel-导入(读取)(read)-示例及核心部件
  • 记录让cursor帮我给ruoyi-vue后台管理项目整合mybatis-plus
  • 第05章 04 VTK标量算法概述
  • 【时时三省】(C语言基础）对比一组函数
  • 如何使用 OpenSSL 检查 Linux 中的 SSL 证书
  • 解决查看服务器ESN（许可证管理）
  • HarmonyOS：MVVM模式
  • 一文大白话讲清楚webpack基本使用——16——图片压缩
  • vscode无法格式化go代码的问题
  • 第24篇：Python开发进阶：掌握Python编程中的调试技巧
  • 【Leetcode 每日一题】40. 组合总和 II