任务处理【华为OD机试】(JAVA&Python&C++&JS题解)

一. 题目-任务处理

在某个项目中有多个任务（用 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. 将任务数组按照结束时间从小到大进行排序。
2. 初始化一个变量 maxTasks 用于记录可以处理的最大任务数，初始值为0。
3. 遍历排序后的任务数组，对于每一个任务，如果任务的开始时间大于等于前一个任务的结束时间，说明可以在同一天处理，增加 maxTasks。
4. 返回 maxTasks 作为结果。

这种贪心的策略保证了每次选择最早结束的任务，从而尽可能地释放出更多的时间来处理其他任务。

在给定示例中，排序后的任务数组为：[[1, 1], [1, 2], [1, 3]]。按照上述策略，可以在第一天处理任务1，第二天处理任务2，第三天处理任务3，总共完成3个任务。

这样的贪心策略保证了每次都选择最早结束的任务，以便为后续的任务留出更多的时间。

三.题解代码

Python题解代码

import heapq

def solve():
    ans = 0
    pq = []  # 使用优先队列作为待处理队列

    for i in range(100005):
        while pq and pq[0] < i:
            heapq.heappop(pq)  # 第一步：移除已经结束的任务

        if i in a:
            for task in a[i]:
                heapq.heappush(pq, task)  # 第二步：将当前时刻开始的任务加入队列

        if pq:
            ans += 1
            heapq.heappop(pq)  # 第三步：从队列中取出结束时间最早的任务，安排在这一天

    return ans


n = int(input())  # 输入任务数量

a = {}  # 存储任务的开始和结束时间

for _ in range(n):
    x, y = map(int, input().split())
    if x in a:
        a[x].append(y)
    else:
        a[x] = [y]

print(solve())

JAVA题解代码

import java.util.*;
 
 
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        int n = Integer.valueOf(in.nextLine());
        List<int[]> list = new ArrayList<int[]>();
        int min = 1;
        int max = 1;
        for (int i = 0; i < n; i++) {
            int s = in.nextInt();
            int e = in.nextInt();
            min = Math.min(s, min);
            max = Math.max(e, max);
            list.add(new int[] {s, e});
        }
        System.out.println(list.size());
        
    }
}

C/C++题解代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> a[100005];

int solve() {
    int ans = 0;
    priority_queue<int, vector<int>, greater<int>> pq; // 使用小顶堆作为待处理队列

    for (int i = 0; i < 100005; i++) {
        while (!pq.empty() && pq.top() < i) {
            pq.pop(); // 第一步：移除已经结束的任务
        }

        if (!a[i].empty()) {
            for (int j = 0; j < a[i].size(); j++) {
                pq.push(a[i][j]); // 第二步：将当前时刻开始的任务加入队列
            }
        }

        if (!pq.empty()) {
            ans++;
            pq.pop(); // 第三步：从队列中取出结束时间最早的任务，安排在这一天
        }
    }

    return ans;
}

int main() {
    int n;
    cin >> n; // 输入任务数量

    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        a[x].push_back(y); // 存储任务的开始和结束时间
    }

    cout << solve() << endl;

    return 0;
}

JS题解代码

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
    input += data;
});
process.stdin.on('end', () => {
    const lines = input.trim().split('\n');
    const n = parseInt(lines[0]);
    const a = new Array(100005).fill().map(() => []);

    for (let i = 1; i <= n; i++) {
        const [x, y] = lines[i].trim().split(' ').map(Number);
        a[x].push(y);
    }

    const solve = () => {
        let ans = 0;
        const pq = [];

        for (let i = 0; i < 100005; i++) {
            while (pq.length > 0 && pq[0] < i) {
                pq.shift();
            }

            if (a[i].length > 0) {
                for (let j = 0; j < a[i].length; j++) {
                    pq.push(a[i][j]);
                }
            }

            if (pq.length > 0) {
                ans++;
                pq.shift();
            }
        }

        return ans;
    };

    const result = solve();
    console.log(result);
});

代码OJ评判结果
通过测试点

四.代码讲解(Java&Python&C++&JS分别讲解)

Python题解代码解析：

1. 导入模块： 使用了 Python 的 heapq 模块，该模块提供了堆队列算法的实现。

2. 解题函数 solve()：

   • 初始化变量 ans 为0，表示最终的答案。
   • 初始化优先队列 pq 作为待处理队列。
   • 遍历时间点 i，在每个时间点：
     • 移除已经结束的任务，即从队列 pq 中弹出小于当前时间点 i 的任务。
     • 将当前时刻开始的任务加入队列 pq。
     • 如果队列 pq 非空，表示可以在这一天处理任务，增加 ans 并从队列中取出结束时间最早的任务。
   • 返回最终的 ans。

3. 输入处理：

   • 输入任务数量 n。
   • 构建字典 a，用于存储任务的开始和结束时间。

4. 任务输入循环：

   • 对于每个任务，读取开始时间 x 和结束时间 y。
   • 将任务加入字典 a 中，如果该时间点已存在则追加任务，否则创建一个新的列表。

5. 输出结果：

   • 调用 solve() 函数计算并打印最大任务数。

JAVA题解代码解析：

1. 导入模块： 使用了 Java 的 Scanner 和 ArrayList。

2. 主函数 main()：

   • 使用 Scanner 读取任务数量 n。
   • 构建 ArrayList 存储任务的开始和结束时间。
   • 计算任务开始和结束时间的最小值 min 和最大值 max。
   • 输出 list 的大小，即任务数量。

C/C++题解代码解析：

1. 导入模块： 使用了 C++ 的 <iostream> 和 <vector>。

2. 解题函数 solve()：

   • 初始化变量 ans 为0，表示最终的答案。
   • 使用小顶堆（priority_queue）作为待处理队列。
   • 遍历时间点 i，在每个时间点：
     • 移除已经结束的任务，即从堆中弹出小于当前时间点 i 的任务。
     • 将当前时刻开始的任务加入堆。
     • 如果堆非空，表示可以在这一天处理任务，增加 ans 并从堆中取出结束时间最早的任务。
   • 返回最终的 ans。

3. 主函数 main()：

   • 读取任务数量 n。
   • 构建数组 a 存储任务的开始和结束时间。
   • 调用 solve() 函数计算并打印最大任务数。

JS题解代码解析：

1. 输入处理：

   • 使用 Node.js 处理标准输入，监听 data 和 end 事件。
   • 将输入的数据转换为数组 lines。

2. 任务处理函数 solve()：

   • 初始化变量 ans 为0，表示最终的答案。
   • 使用数组 pq 作为待处理队列。
   • 遍历时间点 i，在每个时间点：
     • 移除已经结束的任务，即从数组 pq 中移除小于当前时间点 i 的任务。
     • 将当前时刻开始的任务加入数组 pq。
     • 如果数组 pq 非空，表示可以在这一天处理任务，增加 ans 并从数组中取出结束时间最早的任务。
   • 返回最终的 ans。

3. 输入处理：

   • 通过 process.stdin 读取输入，处理每一行的任务开始和结束时间。
   • 构建数组 a 存储任务的开始和结束时间。

4. 输出结果：

   • 调用 solve() 函数计算并打印最大任务数。

寄语