机器任务调度

题目描述

某系统中共有 $m$ 台机器，机器分为 $3$ 种类型。现有 $n$ 个任务依次到达，每个任务只能由与其类型对应的机器处理。

每个任务具有以下属性：

到达时间 $time$
所需机器类型 $type$
执行时长 $last$
优先级 $priority$

任务按照到达时间非递减顺序给出，即：

time_i \le time_{i+1}

当任务到达时，如果对应类型存在空闲机器，则该任务可以参与调度；如果当前没有空闲的对应类型机器，则任务进入该类型的等待队列。

当某一类型存在空闲机器时，需要从该类型所有已经到达但尚未执行的任务中选择任务执行。任务选择规则依次如下：

优先级 $priority$ 更高的任务优先；
若优先级相同，则到达时间 $time$ 更早的任务优先；
若到达时间也相同，则任务编号更小的任务优先。

任务编号按照输入顺序从 $1$ 到 $n$ 编号。

任务一旦开始执行，中途不会被其他任务抢占。若某任务在时刻 $t$ 开始执行，执行时长为 $last$ ，则其结束时间为：

finish = t + last

任务在时刻 $finish$ 执行结束，对应机器同时恢复为空闲状态，并可以立即处理其他任务。

保证每个任务都至少存在一台对应类型的机器。

请计算每个任务的开始执行时间和结束时间，并按照任务编号从小到大的顺序输出。

输入描述

第一行输入两个整数：

m n

分别表示机器数量和任务数量。

第二行输入 $m$ 个整数：

a1 a2 ... am

其中 $a_i$ 表示第 $i$ 台机器的类型，且：

a_i \in \{1,2,3\}

接下来输入 $n$ 行，每行包含四个整数：

time type last priority

分别表示当前任务的到达时间、所需机器类型、执行时长和优先级。

第 $i$ 行任务的编号为 $i$ 。

所有任务按照到达时间非递减顺序输入。

输出描述

输出 $n$ 行。

第 $i$ 行输出两个整数：

start finish

分别表示第 $i$ 个任务的开始执行时间和结束时间。

数据范围

1 \le m,n < 2\times 10^5

1 \le type \le 3

0 \le time < 10^9

0 < last < 10^9

0 \le priority < 10^9

保证每个任务均存在至少一台对应类型的机器。

题解

1. 题目分析

系统中共有 $m$ 台机器，机器分为 $3$ 种类型，同时有 $n$ 个任务按照到达时间非递减的顺序到达。

每个任务包含到达时间 $time$ 、所需机器类型 $type$ 、执行时长 $last$ 和优先级 $priority$ 。任务只能由对应类型的机器执行。

当任务到达后，如果对应类型存在空闲机器，则可以参与调度；如果没有空闲机器，则进入等待队列。当某类机器空闲时，需要从当前等待该类型机器的任务中选择一个执行，选择规则依次为：

优先级 $priority$ 更高的任务优先；
优先级相同时，到达时间 $time$ 更早的任务优先；
到达时间仍然相同时，任务编号更小的任务优先。

任务一旦开始执行便不会被抢占。若任务在时刻 $t$ 开始执行，执行时长为 $last$ ，则结束时间为：

finish=t+last

任务结束后，对应机器立即重新变为空闲状态。

本题的数据范围为：

m,n<2\times10^5

同时：

time,last,priority<10^9

因此需要重点考虑模拟方式和数据结构的效率。

2. 逐时刻模拟的问题

最直观的做法是维护当前时间 $t$ ，每次令 $t$ 增加 $1$ ，然后检查当前是否有任务到达、是否有机器释放，以及是否能够调度等待任务。

这种方法虽然容易理解，但无法通过本题的数据范围。

因为任务到达时间和执行时间最大可以接近 $10^9$ 。如果两个事件之间相隔很远，例如当前事件发生在时刻 $1$ ，下一个事件发生在时刻 $10^9$ ，逐时刻模拟就需要进行接近 $10^9$ 次没有意义的循环。

实际上，两个事件之间系统状态并不会发生任何变化，因此没有必要处理其中的每一个时间点。

本题更适合使用事件驱动模拟。

3. 事件驱动模拟

整个调度系统中，只有两种事件会改变系统状态：

新任务到达；
某个正在执行的任务结束，对应机器被释放。

因此，只需要依次处理这些事件发生的时刻。

假设下一个尚未处理的任务到达时间为：

T_a

当前正在运行的任务中，最早结束时间为：

T_f

那么下一个需要处理的时间就是：

T=\min(T_a,T_f)

直接将当前时间跳转到 $T$ 即可，不需要处理两个事件之间的所有整数时间。

这样，算法复杂度就不再与时间值的大小有关，而只与任务数量有关。

4. 等待任务的维护

机器只有 $3$ 种类型，因此可以分别维护三个等待队列。

对于某一种机器类型，当机器出现空闲时，需要快速找出当前最应该执行的任务。

题目的任务选择规则为：

priority\ 降序

优先级相同时：

time\ 升序

到达时间仍然相同时：

num\ 升序

因此可以为每种机器类型维护一个优先队列。

优先队列的堆顶始终保存该类型当前优先级最高的等待任务。

这样，每次机器空闲时，不需要遍历全部等待任务寻找最优任务，只需要直接取出优先队列的堆顶即可。

任务进入和离开优先队列的时间复杂度均为：

O(\log n)

5. 机器释放事件的维护

任务开始执行后，对应机器会在未来某个时刻重新变为空闲。

若任务在时刻 $t$ 开始执行，执行时长为 $last$ ，则机器释放时间为：

t+last

因此，每开始执行一个任务，就会产生一个新的“机器释放事件”。

为了快速找到下一台即将释放的机器，可以维护一个按照结束时间从小到大排列的小根堆。

每个机器释放事件只需要记录两个信息：

机器释放时间；
机器类型。

堆顶始终是当前最早发生的机器释放事件。

因此，下一个机器释放时间可以在 $O(1)$ 时间内获得，插入和删除事件的复杂度为：

O(\log n)

6. 同一时刻的处理顺序

对于某个事件时刻 $t$ ，需要严格按照以下顺序处理：

释放所有在 $t$ 时刻执行结束的机器；
将所有在 $t$ 时刻到达的新任务加入对应等待队列；
使用当前所有空闲机器调度等待任务。

这个顺序非常重要。

首先，若某个任务恰好在 $t$ 时刻结束，那么对应机器应该能够立即参与 $t$ 时刻的新一轮调度，因此必须先处理机器释放。

其次，同一时刻可能有多个任务同时到达。必须先将这些任务全部加入等待队列，再按照优先级统一选择。

例如只有一台机器，在时刻 $5$ 同时到达两个任务，其中任务 1 的优先级为 $1$ ，任务 2 的优先级为 $10$ 。

虽然任务 1 的输入顺序更靠前，但两个任务实际上是同时到达的，因此应该先将二者都加入等待队列，再选择优先级更高的任务 2 执行。

如果读取一个任务后立即进行调度，就可能错误地让任务 1 提前占用机器。

7. 调度过程

对于每种机器类型，维护当前空闲机器数量。

在处理完当前时刻的机器释放和任务到达事件后，对三种机器分别进行调度。

只要某种类型同时满足：

当前还有空闲机器；
当前还有等待任务；

就不断从该类型的等待优先队列中取出优先级最高的任务执行。

假设当前事件时间为 $t$ ，取出的任务执行时长为 $last$ ，那么：

start=t

finish=t+last

记录该任务的开始时间和结束时间后，当前类型的空闲机器数量减少 $1$ 。

同时，将新的机器释放事件：

(finish,type)

加入运行事件的小根堆。

当时间推进到 $finish$ 时，再将对应类型的空闲机器数量增加 $1$ 。

8. 为什么不需要记录每台具体机器

虽然系统中共有 $m$ 台机器，但同一种类型的机器之间没有任何区别。

例如某种类型有 $10$ 台机器，题目只关心某个任务什么时候开始和结束，并不要求输出任务具体运行在哪一台机器上。

因此没有必要维护每台机器的独立状态，只需要记录三种机器当前分别有多少台空闲即可。

这样机器状态只需要三个整数即可维护。

9. 时间类型的选择

虽然题目给出的单个到达时间和执行时长均满足：

time,last<10^9

但任务可能产生长时间排队。

例如只有一台机器，同时有接近 $2\times10^5$ 个任务依次执行，每个任务的执行时长都接近 $10^9$ ，最终任务的结束时间可能达到：

2\times10^5\times10^9 = 2\times10^{14}

这一数值已经远远超过 $32$ 位整数的表示范围。

因此，与时间有关的数据，包括到达时间、执行时长、开始时间和结束时间，都应该使用 long long 保存。

10. 完整代码

#include <iostream>
#include <vector>
#include <queue>
#include <functional>

using namespace std;

struct Task {
    int num;
    long long time;
    int type;
    long long last;
    long long priority;
};

struct TaskCompare {
    bool operator()(const Task& a, const Task& b) const {
        if (a.priority != b.priority) {
            return a.priority < b.priority;
        }

        if (a.time != b.time) {
            return a.time > b.time;
        }

        return a.num > b.num;
    }
};

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

    // 三种机器当前的空闲数量
    vector<int> available(3, 0);

    for (int i = 0; i < m; ++i) {
        int type;
        cin >> type;
        available[type - 1]++;
    }

    // 保存所有任务
    vector<Task> tasks(n);

    for (int i = 0; i < n; ++i) {
        cin >> tasks[i].time
            >> tasks[i].type
            >> tasks[i].last
            >> tasks[i].priority;

        tasks[i].num = i;

        // 将类型从 1、2、3 转换为 0、1、2
        tasks[i].type--;
    }

    // 三种机器分别维护自己的等待任务
    priority_queue<
        Task,
        vector<Task>,
        TaskCompare
    > wait[3];

    // 正在执行任务的结束事件
    // first：结束时间
    // second：机器类型
    priority_queue<
        pair<long long, int>,
        vector<pair<long long, int>>,
        greater<pair<long long, int>>
    > running;

    // result[i] = {开始时间, 结束时间}
    vector<pair<long long, long long>> result(n);

    // 下一个还没有进入等待队列的任务
    int index = 0;

    while (index < n || !running.empty()) {
        long long currentTime;

        // 确定下一个事件发生的时间
        if (index < n && !running.empty()) {
            currentTime = min(
                tasks[index].time,
                running.top().first
            );
        }
        else if (index < n) {
            currentTime = tasks[index].time;
        }
        else {
            currentTime = running.top().first;
        }

        // 1. 释放所有当前时刻结束任务的机器
        while (!running.empty()
               && running.top().first == currentTime) {

            int type = running.top().second;
            running.pop();

            available[type]++;
        }

        // 2. 加入所有当前时刻到达的任务
        while (index < n
               && tasks[index].time == currentTime) {

            int type = tasks[index].type;

            wait[type].push(tasks[index]);

            index++;
        }

        // 3. 使用当前空闲机器调度等待任务
        for (int type = 0; type < 3; ++type) {

            while (available[type] > 0
                   && !wait[type].empty()) {

                Task task = wait[type].top();
                wait[type].pop();

                long long start = currentTime;
                long long finish = start + task.last;

                result[task.num] = {
                    start,
                    finish
                };

                // 占用一台机器
                available[type]--;

                // 加入未来的机器释放事件
                running.push({
                    finish,
                    type
                });
            }
        }
    }

    // 按任务原始编号输出
    for (int i = 0; i < n; ++i) {
        cout << result[i].first
             << " "
             << result[i].second
             << '\n';
    }

    return 0;
}

11. 正确性分析

考虑任意事件时刻 $t$ 。

算法首先释放所有在 $t$ 时刻执行结束的机器，因此在正式调度之前，所有在 $t$ 时刻已经可用的机器都会被正确统计为空闲状态。

随后，算法将所有在 $t$ 时刻到达的任务统一加入等待队列。因此，同一时刻到达的任务能够按照优先级统一参与竞争，不会受到输入读取顺序的影响。

对于某一种机器类型，其等待队列始终按照题目要求维护：

priority\ 降序

time\ 升序

num\ 升序

因此每次从堆顶取出的任务一定是当前所有等待任务中最应该被执行的任务。

每开始执行一个任务，就立即减少一台对应类型的空闲机器，并在其结束时间产生机器释放事件。因此，在任务执行期间该机器不会被重复使用，而在任务结束时又能够正确恢复为空闲状态。

所以算法在每一个事件时刻产生的调度结果都与题目规则一致，最终可以得到所有任务正确的开始时间和结束时间。

12. 复杂度分析

每个任务最多进行以下操作：

进入等待任务优先队列一次；
从等待任务优先队列弹出一次；
产生一个机器释放事件；
机器释放事件从小根堆弹出一次。

每次优先队列操作的时间复杂度为：

O(\log n)

因此所有任务的总时间复杂度为：

O(n\log n)

统计机器类型需要：

O(m)

因此总时间复杂度为：

\boxed{O(m+n\log n)}

所有任务、等待队列、运行事件以及结果数组最多保存 $O(n)$ 规模的数据，因此空间复杂度为：

\boxed{O(n)}

对于：

m,n<2\times10^5

该算法可以满足要求。