题目链接

任务安排

题目描述

有 N 个任务，每个任务都需要一个单位时间来完成。第 i 个任务有截止时间 d_i 和收益 p_i。只有在截止时间前（含）完成任务，才能获得相应收益。在任何时刻只能进行一项任务。求能够获得的最大总收益。

解题思路

这是一个经典的调度问题，可以使用贪心算法来高效解决。由于任务的截止时间 d_i 范围很大（高达 ），直接使用与时间点相关的数组会导致内存超限，因此我们需要一种不依赖于截止时间大小的算法。

核心贪心策略

一个直观的想法是，截止时间早的任务更“紧急”，我们应该优先考虑它们。

  1. 按截止时间排序：我们将所有任务按照截止时间 d 从小到大排序。这使得我们总是先处理那些必须尽早完成的任务。

  2. 动态选择与“反悔”：我们按排好序的顺序遍历任务。在遍历过程中，我们维护一个已选任务的集合，并记录当前已经花费的时间 time。

    • 对于当前任务 i（截止时间为 d_i，收益为 p_i）：
      • 如果时间允许 (time < d_i)：说明我们可以在截止时间前完成这个任务。我们暂时将其列入计划，将 time 增加 1，并将它的收益 p_i 放入一个数据结构中。
      • 如果时间不允许 (time >= d_i)：我们无法在不违反截止时间的情况下再增加一个任务。但是，我们可以“反悔”。如果当前任务 i 的收益 p_i 比我们已选任务中收益最低的那个还要高，那么放弃那个低收益任务，转而执行当前这个高收益任务，显然是更优的选择。

  3. 使用最小堆优化：为了能够快速找到并替换“已选任务中收益最低的那个”，最小堆（优先队列） 是最合适的数据结构。

完整算法

  1. 将所有任务按照截止时间 d 从小到大排序。
  2. 初始化一个空的最小堆 pq 用于存储已选任务的收益，以及一个 total_profit = 0。
  3. 遍历排序后的任务 (d_i, p_i)： a. 如果当前已选任务数 pq.size() 小于 d_i，说明有时间完成当前任务。将 p_i 推入堆中。 b. 如果 pq.size() 不小于 d_i，并且堆不为空，检查堆顶（即已选任务的最小收益 min_p）。如果 p_i > min_p，则弹出堆顶，并将 p_i 推入堆中。这相当于用高收益任务替换了低收益任务。
  4. 遍历结束后，堆中所有元素的和即为最大总收益。

代码

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

using namespace std;

struct Task {
    int d, p;
};

bool compareTasks(const Task& a, const Task& b) {
    return a.d < b.d;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<Task> tasks(n);
    for (int i = 0; i < n; ++i) {
        cin >> tasks[i].d >> tasks[i].p;
    }

    sort(tasks.begin(), tasks.end(), compareTasks);

    priority_queue<int, vector<int>, greater<int>> pq; // Min-heap

    for (const auto& task : tasks) {
        if (pq.size() < task.d) {
            pq.push(task.p);
        } else {
            if (!pq.empty() && task.p > pq.top()) {
                pq.pop();
                pq.push(task.p);
            }
        }
    }

    long long total_profit = 0;
    while (!pq.empty()) {
        total_profit += pq.top();
        pq.pop();
    }

    cout << total_profit << endl;

    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    static class Task {
        int d, p;
        Task(int d, int p) {
            this.d = d;
            this.p = p;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        Task[] tasks = new Task[n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int d = Integer.parseInt(st.nextToken());
            int p = Integer.parseInt(st.nextToken());
            tasks[i] = new Task(d, p);
        }

        Arrays.sort(tasks, Comparator.comparingInt(a -> a.d));

        PriorityQueue<Integer> pq = new PriorityQueue<>(); // Min-heap

        for (Task task : tasks) {
            if (pq.size() < task.d) {
                pq.add(task.p);
            } else {
                if (!pq.isEmpty() && task.p > pq.peek()) {
                    pq.poll();
                    pq.add(task.p);
                }
            }
        }

        long totalProfit = 0;
        for (int profit : pq) {
            totalProfit += profit;
        }
        
        PrintWriter out = new PrintWriter(System.out);
        out.println(totalProfit);
        out.flush();
    }
}

import sys
import heapq

def solve():
    try:
        n_str = sys.stdin.readline()
        if not n_str: return
        n = int(n_str)
        tasks = []
        for _ in range(n):
            d, p = map(int, sys.stdin.readline().split())
            tasks.append((d, p))
    except (IOError, ValueError):
        return

    # Sort tasks by deadline ascending
    tasks.sort(key=lambda x: x[0])

    # Min-heap to store profits of selected tasks
    pq = [] 
    
    for d, p in tasks:
        if len(pq) < d:
            heapq.heappush(pq, p)
        else:
            # The heap is full for this deadline, check for replacement
            if pq and p > pq[0]:
                heapq.heappop(pq)
                heapq.heappush(pq, p)

    total_profit = sum(pq)
    print(total_profit)

solve()

算法及复杂度

  • 算法：贪心 + 优先队列（最小堆）
  • 时间复杂度：，其中 是任务数。
    • 来自于对任务按截止时间排序。
    • 遍历 N 个任务，每次对优先队列（大小最多为 N）进行操作，复杂度为 。因此循环部分总复杂度为 。
  • 空间复杂度：，用于存储任务和优先队列。