任务处理 - 华为OD统一考试(C卷)

OD统一考试(C卷)

分值: 200分

题解: Java / Python / C++

alt

题目描述

在某个项目中有多个任务(用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. 使用一个小根堆(优先队列)pq,用于保存当前可以执行的任务的截止时间。
  3. 遍历每一天,将当天开始的任务加入小根堆,同时弹出已经过期的任务。
  4. 在小根堆中选择距离截止时间最近的任务进行处理,每次处理后将该任务从小根堆中弹出。
  5. 统计处理的任务数量即为最大任务数。

最后,输出最大任务数即为题目要求的结果。

时间复杂度分析:

假设任务数量为n,排序的时间复杂度为O(nlogn),遍历每一天的时间复杂度为O(100000),而在每一天内对小根堆进行插入和弹出的操作的时间复杂度为O(logn),所以总的时间复杂度为O(nlogn + 100000logn)。由于100000logn相对于nlogn的影响较小,可以近似看作O(nlogn)。

空间复杂度分析:

除了输入和输出所需的空间外,额外使用了一个小根堆来存储任务的截止时间,因此空间复杂度为O(n)。

Java

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

/**
 * @author code5bug
 */
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] tasks = new int[n][2];

        for (int i = 0; i < n; i++) {
            tasks[i][0] = in.nextInt();
            tasks[i][1] = in.nextInt();
        }
        Arrays.sort(tasks, (a, b) -> a[0] - b[0]);

        // 小根堆,保存当前可以执行的任务的截止时间
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        int idx = 0, result = 0;
        for (int now = 1; now <= 100000 + 5; now++) {
            // 当前 tasks[idx] 任务可以在 now 天完成
            while (idx < n && tasks[idx][0] <= now) {
                pq.add(tasks[idx][1]);
                idx++;
            }

            // 当前时间已经超过了任务的结束时间,则任务不可能被执行则抛弃掉
            while (!pq.isEmpty() && pq.peek() < now) {
                pq.poll();
            }

            // 当前时间贪心的选择距离截止时间最近的任务
            if (!pq.isEmpty()) {
                result++;
                pq.poll();
            }
        }

        System.out.println(result);
    }
}

Python

from heapq import heappush
from heapq import heappop


n = int(input())
tasks = [list(map(int, input().split())) for _ in range(n)]
tasks.sort()

# 小根堆,保存当前可以执行的任务的截止时间
pq = []

idx, result = 0, 0
for now in range(1, 100000 + 5):
    # 当前 tasks[idx] 任务可以在 now 天完成
    while idx < n and tasks[idx][0] <= now:
        heappush(pq, tasks[idx][1])
        idx += 1

    # 当前时间已经超过了任务的结束时间,则任务不可能被执行则抛弃掉
    while pq and pq[0] < now:
        heappop(pq)

    # 当前时间贪心的选择距离截止时间最近的任务
    if pq:
        result += 1
        heappop(pq)

print(result)

C++

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

using namespace std;

int main() {
    int n;
    cin >> n;

    // 保存任务的开始时间和截止时间的pair
    vector<pair<int, int>> tasks(n);

    // 输入任务信息并按截止时间排序
    for (int i = 0; i < n; ++i) {
        cin >> tasks[i].first >> tasks[i].second;
    }
    sort(tasks.begin(), tasks.end());

    // 小根堆,保存当前可以执行的任务的截止时间
    priority_queue<int, vector<int>, greater<int>> pq;

    int idx = 0, result = 0;
    for (int now = 1; now <= 100000 + 5; ++now) {
        // 当前 tasks[idx] 任务可以在 now 天完成
        while (idx < n && tasks[idx].first <= now) {
            pq.push(tasks[idx].second);
            idx++;
        }

        // 当前时间已经超过了任务的结束时间,则任务不可能被执行则抛弃掉
        while (!pq.empty() && pq.top() < now) {
            pq.pop();
        }

        // 当前时间贪心的选择距离截止时间最近的任务
        if (!pq.empty()) {
            result++;
            pq.pop();
        }
    }

    cout << result << endl;

    return 0;
}

🙏整理题解不易, 如果有帮助到您,请给点个赞 ‍❤️‍ 和收藏 ⭐,让更多的人看到。🙏🙏🙏

#面经##春招##校招##笔试##华为#
全部评论
java方法是不是有错误 超过任务结束时间的判断应该是 !pq.isEmpty() && pq.peek() > now 吧 不然输入 3 1 1 1 2 1 2 也是输出的3
点赞 回复 分享
发布于 2024-10-13 14:44 江苏
1、先比较开始时间再比较结束时间排序 2、定义大小为maxEnd-minStart的数组用于标识第n天是否已经执行过任务 3、循环排序列表,如果可以存放start,设置游标index为当前start+1;如果不可以存放在start且end>=index说明可以存放在index中 4、统计存放过的数据和
点赞 回复 分享
发布于 2024-09-30 18:22 上海
now <= 100000 + 5 ;为什么要加5呢?
点赞 回复 分享
发布于 2024-08-08 21:25 上海

相关推荐

评论
6
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务