最新华为OD机试真题-任务安排问题(200分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

任务安排问题(200分)

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

🫐 任务安排问题

问题描述

LYA是一家公司的项目经理,她需要安排公司的多个项目任务。每个任务都有一个开始时间和结束时间。LYA希望在给定的时间范围内安排尽可能多的任务。

具体来说,给定一个任务列表 ,其中 表示第 个任务的开始时间为 ,结束时间为 。LYA可以在 的任意一天处理该任务。请帮助 LYA找出她可以处理的最大任务数。

输入格式

第一行包含一个正整数 ,表示任务的数量,。

接下来 行,每行包含两个正整数 和 ,表示第 个任务的开始时间和结束时间,。

输出格式

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

样例输入

3
1 1
1 2
1 3

样例输出

3

样例解释

LYA可以在第 1 天处理所有三个任务。

数据范围

题解

这个问题可以用贪心算法和优先队列来解决。我们遍历时间轴上的每一天,维护一个优先队列存储当前可以处理的任务的结束时间。对于每一天,首先移除队列中已经结束的任务,然后将当天开始的新任务加入队列,最后从队列中取出一个结束时间最早的任务进行处理。

这样做的原因是,对于一个给定的日期,总是希望处理结束时间最早的任务,因为这样可以最大化后续能够处理的任务数量。通过优先队列,可以在对数时间内找到结束时间最早的任务。

该算法的时间复杂度为 ,空间复杂度为 ,其中 是任务的数量。

参考代码

• Python

import heapq

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

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

        if day in tasks:
            for end_day in tasks[day]:
                heapq.heappush(pq, end_day)  # 将当前时刻开始的任务加入队列

        if pq:
            max_tasks += 1
            heapq.heappop(pq)  # 从队列中取出结束时间最早的任务

    return max_tasks


n = int(input())  # 输入任务数量
tasks = {}  # 存储任务的开始和结束时间

for _ in range(n):
    start, end = map(int, input().split())
    if start in tasks:
        tasks[start].append(end)
    else:
        tasks[start] = [end]

print(solve(tasks))

• Java

import java.util.*;

public class Main {
    public static int solve(Map<Integer, List<Integer>> tasks) {
        int maxTasks = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int day = 1; day <= 100005; day++) {
            while (!pq.isEmpty() && pq.peek() < day) {
                pq.poll(); // 移除已经结束的任务
            }

            if (tasks.containsKey(day)) {
                for (int endDay : tasks.get(day)) {
                    pq.offer(endDay); // 将当前时刻开始的任务加入队列
                }
            }

            if (!pq.isEmpty()) {
                maxTasks++;
                pq.poll(); // 从队列中取出结束时间最早的任务
            }
        }

        return maxTasks;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Map<Integer, List<Integer>> tasks = new HashMap<>();

        for (int i = 0; i < n; i++) {
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            tasks.computeIfAbsent(start, k -> new ArrayList<>()).add(end);
        }

        System.out.println(solve(tasks));
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;

int solve(unordered_map<int, vector<int>>& tasks) {
    int max_tasks = 0;
    priority_queue<int, vector<int>, greater<int>> pq;

    for (int day = 1; day <= 100005; day++) {
        while (!pq.empty() && pq.top() < day) {
            pq.pop(); // 移除已经结束的任务
        }

        if (tasks.count(day)) {
            for (int end_day : tasks[day]) {
                pq.push(end_day); // 将当前时刻开始的任务加入队列
            }
        }

        if (!pq.empty()) {
            max_tasks++;
            pq.pop(); // 从队列中取出结束时间最早的任务
        }
    }

    return max_tasks;
}

int main() {
    int n;
    cin >> n;
    unordered_map<int, vector<int>> tasks;

    for (int i = 0; i < n; i++) {
        int start, end;
        cin >> start >> end;
        tasks[start].push_back(end);
    }

    cout << solve(tasks) << endl;
    return 0;
}