2024年华为OD机试真题-任务处理

华为OD机试真题-任务处理-2024年OD统一考试（D卷）

题目描述：

在某个项目中有多个任务（用 tasks 数组表示）需要您进行处理，其中 tasks[i] = [si, ei]，你可以在 si <= day <= ei 中的任意一天处理该任务。请返回你可以处理的最大任务数。

注：一天可以完成一个任务的处理。

输入描述：

第一行为任务数量 n，1 <= n <= 100000。后面 n 行表示各个任务的开始时间和终止时间，用 si 和 ei 表示，1 <= si <= ei <= 100000。

输出描述：

输出为一个整数，表示可以处理的最大任务数。

补充说明：

示例1

输入：

3

1 1

1 2

1 3

输出：

3

说明：

第一天处理任务 1，第二天处理任务 2，第三天处理任务 3。

解题思路：

一个简单的贪心问题，要尽可能处理多的任务，我们要优先处理当前可以处理且最早结束的任务，使用一个小根堆来维护当前我们最应该处理的任务，在处理完成之后天数加1，然后更新我们的小根堆，剔除过期的任务，增加新一天可以完成的任务。

Java代码：

import java.util.*; 
 
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in); // 创建扫描器对象以接收输入
        List<Integer>[] cod = new List[100005]; // 创建一个列表数组，存储每个开始时间对应的结束时间
        for (int i=0; i<cod.length; i++)
            cod[i] = new ArrayList<>(); // 初始化每个列表
        int n = in.nextInt(); // 读取任务数量
        for (int i = 0; i < n; i++) {
            int s = in.nextInt(), t = in.nextInt(); // 读取每个任务的开始和结束时间
            cod[s].add(t); // 将结束时间添加到对应的开始时间列表中
        }
        int ans = 0; // 用于记录可以完成的最大任务数
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 创建一个优先队列（最小堆）来存储当前可完成任务的结束时间
        for (int i = 1; i <= (int)1e5; i++) { // 遍历每一天
            for (int t : cod[i]) // 将当前天数开始的所有任务的结束时间加入到最小堆中
                minHeap.add(t);
            while (!minHeap.isEmpty() && minHeap.peek() < i) // 清除所有已经不能完成的任务（结束时间已经过去的任务）
                minHeap.poll();
            if (!minHeap.isEmpty()) { //