题面描述

设计一个简单的任务调度器，支持两种操作：

1. 添加任务：格式为

   add task_id priority time
   

   • $task\_id\in[0,65535]$：任务唯一标识
   • $priority\in[0,99]$：优先级，数值越小优先级越高
   • $time\in[1,10000]$：需要的时间片数量
2. 运行调度：格式为

   run T
   

   • 消耗 $T\in[1,100000]$ 个时间片，调度器每次选取当前队列中优先级最低的任务执行，执行过程中如果有新任务加入且比当前运行任务优先级更高，则会抢占。
     仅在 最后一次 run 操作完成后，输出此时正在调度的任务 $ID$，若无任务则输出 idle。

思路

使用一个优先队列维护所有就绪任务，队列排序依据：

1. 首先按 $priority$ 升序（越小越先调度）
2. 若 $priority$ 相同，则按到达顺序（FIFO）

每当执行 run T：

• 不断从队列中取出队首任务，计算其剩余运行时间与 $T$ 的比较，消耗相应时间片：
  • 若任务能在本次运行内完成，则 $T$ 减去已消耗时间，丢弃该任务，继续调度下一个。
  • 若任务未完成，则更新其剩余时间并重新入队（保持其到达时序不变），结束本次 run。
    中间不输出任何结果，仅在最后一次 run 结束后，检查队列头并打印对应的 $task\_id$ 或 idle。

代码分析

1. 数据结构：
   • struct Task { int id, prio, rem, order; };
   • 使用 std::priority_queue 或 std::set 实现，保证 $O(\log N)$ 的入队和出队。
2. 抢占模拟：
   • 运行过程中，随时可有新的 add 操作插入队列，因优先队列性质会自动对比优先级并决定是否抢占。
3. 输出控制：
   • 记录每次 run 是否为最后一次，只有最后一次执行结束后才打印结果。

问题本质分析

• 本质：多级优先队列调度＋抢占式执行的模拟。
• 难点：正确处理多次 run 的状态累积，以及只在最后一次打印结果。
• 复杂度：每条操作 $O(\log N)$，总操作数 $\le10000$，可在严格时间内完成。

C++ 实现

#include <bits/stdc++.h>
using namespace std;

// 任务结构体
struct Task {
    int id;     // 任务ID
    int prio;   // 优先级（越小越先）
    int rem;    // 剩余时间片
    int order;  // 到达顺序
};

// 优先队列比较器
struct Cmp {
    bool operator()(const Task &a, const Task &b) const {
        if (a.prio != b.prio) return a.prio > b.prio;
        return a.order > b.order;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    priority_queue<Task, vector<Task>, Cmp> pq;
    string cmd;
    int next_order = 0;
    vector<pair<string, vector<int>>> ops;

    // 读取所有操作
    while (getline(cin, cmd)) {
        if (cmd.empty()) break;
        stringstream ss(cmd);
        string op; ss >> op;
        if (op == "add") {
            int id, p, t; ss >> id >> p >> t;
            ops.push_back({op, {id, p, t}});
        } else if (op == "run") {
            int T; ss >> T;
            ops.push_back({op, {T}});
        }
    }

    // 模拟所有操作，只在最后一次 run 后输出
    int last_run_idx = -1;
    for (int i = 0; i < (int)ops.size(); i++) {
        if (ops[i].first == "run") last_run_idx = i;
    }

    for (int i = 0; i < (int)ops.size(); i++) {
        auto &op = ops[i];
        if (op.first == "add") {
            // 入队一个新任务
            pq.push({op.second[0], op.second[1], op.second[2], next_order++});
        } else {
            int T = op.second[0];
            while (T > 0 && !pq.empty()) {
                Task t = pq.top(); pq.pop();
                if (t.rem <= T) {
                    T -= t.rem;  // 任务完成，消耗全部剩余时间
                } else {
                    t.rem -= T;  // 任务未完成，更新剩余时间
                    T = 0;
                    pq.push(t);  // 重新入队
                }
            }
            // 如果是最后一次 run，输出结果
            if (i == last_run_idx) {
                if (pq.empty()) cout << "idle\n";
                else cout << pq.top().id << "\n";
            }
        }
    }
    return 0;
}

Python 实现

import sys
import heapq

def main():
    pq = []  # 优先队列：元素为 (prio, order, id, rem)
    order = 0
    ops = []

    # 读取输入
    for line in sys.stdin:
        line = line.strip()
        if not line:
            break
        parts = line.split()
        ops.append(parts)

    # 找到最后一次 run 的索引
    last_run = max(i for i, op in enumerate(ops) if op[0] == "run")

    # 模拟
    for i, op in enumerate(ops):
        if op[0] == "add":
            _, tid, p, t = op
            heapq.heappush(pq, (int(p), order, int(tid), int(t)))
            order += 1
        else:  # run
            T = int(op[1])
            while T > 0 and pq:
                p, ord_v, tid, rem = heapq.heappop(pq)
                if rem <= T:
                    T -= rem
                else:
                    rem -= T
                    T = 0
                    heapq.heappush(pq, (p, ord_v, tid, rem))
            if i == last_run:
                if not pq:
                    print("idle")
                else:
                    print(pq[0][2])

if __name__ == "__main__":
    main()

Java 实现

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static class Task {
        int id, prio, rem, order;
        Task(int id, int prio, int rem, int order) {
            this.id = id;
            this.prio = prio;
            this.rem = rem;
            this.order = order;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Task> pq = new PriorityQueue<>(
            (a, b) -> a.prio != b.prio ? a.prio - b.prio : a.order - b.order
        );
        List<String[]> ops = new ArrayList<>();
        String line;
        while ((line = br.readLine()) != null && !line.isEmpty()) {
            ops.add(line.split("\\s+"));
        }

        // 找到最后一次 run
        int lastRun = -1;
        for (int i = 0; i < ops.size(); i++) {
            if (ops.get(i)[0].equals("run")) lastRun = i;
        }

        int order = 0;
        for (int i = 0; i < ops.size(); i++) {
            String[] op = ops.get(i);
            if (op[0].equals("add")) {
                int id = Integer.parseInt(op[1]);
                int p  = Integer.parseInt(op[2]);
                int t  = Integer.parseInt(op[3]);
                pq.offer(new Task(id, p, t, order++));
            } else {
                int T = Integer.parseInt(op[1]);
                while (T > 0 && !pq.isEmpty()) {
                    Task t = pq.poll();
                    if (t.rem <= T) {
                        T -= t.rem;
                    } else {
                        t.rem -= T;
                        T = 0;
                        pq.offer(t);
                    }
                }
                if (i == lastRun) {
                    if (pq.isEmpty()) {
                        System.out.println("idle");
                    } else {
                        System.out.println(pq.peek().id);
                    }
                }
            }
        }
    }
}

题目内容

你需要开发一个简单的任务调度系统，该系统按任务优先级进行调度，优先级范围是$(0,99)$，数值越小优先级越高。只有高优头级任务执行完成后，低优先级任务才能执行，同等优先级的任务，按照$FIFO$原则，先进入调度系统的任务会优先调度，当优先级任务执行时，如新增了高优先级任务，高优先级任务会抢占低优先级任务。

请实现一个程序，模拟这个任务调度系统，

程序需要完成以下功能:

$1$.添加任务:将一个新任务添加到任务调度系统，任务包含一个唯一$ID$$(task$_$id$)$[0,65535]$，优先级$(priority)[0,99]$，运行时间$(time)[1,10000]$。运行时间的单位可以认为是一个时间片单元，无需关心单位。

2.执行任务:任务调度系统按照调度策略，调度任务并执行，调度系统

调度任务:并消耗对应时间片，时间片范围$[1,100000]$

输入描述

输入格式

程序需要处理以下类型的输入:

1.添加任务 $add\ task$_$id\ priority\ time$

2.执行任务

$run\ time$

注

$1$.输入命令总行数不超过$10000$行

$2$.$run$命令可以有多个

$3$.空行即命令结束

输出描述

显示任务调度系统当前执行的任务$ID$。若无任何任务，则显示$idle$。

样例1

输入

add 101 0 10
add 20 1 3
add 300 0 1
run 11

输出

20

说明

$add\ 101\ 0\ 10$:添加任务$101$，其优先级为$0$，运行时间为$10$个时网片

$add\ 20\ 1\ 3$:添加任务$20$，其优先级为$1$，运行时间为$3$个时时间片

$add\ 300\ 0\ 1$:添加任务$300$，其优先级为$0$，运行时间为$1$个时间片

$run11$:调度系统调度任务并执行。首先调度任务$101$，运行了$10$个时间片，任务完成。接下来调度任务$300$(其优先级高于任务$20$)，返行了$1$个时间片，任务完成。此时消耗完全部运行时间片(即$11$)

此时调度系统要运行的任务$id$即为$20$

样例2

输入

add 1 0 10
run 11

输出

idle

说明

$add\ 1\ 1\ 15$:添加任务$1$，优先级$0$，运行为$10$个时间片

$run\ 11$:调度系统调度任务，并运行$11$个时间片。选择任务运行$10$个时间片。任务$1$完成,无任务待调度

调度系统无任何任务，因此显示$idle$

样例3

输入

add 1 1 15 
run 11
add 2 0 6
run 3

输出

2

说明

$add\ 1\ 1\ 15$:添加任务$1$，优先级$1$，运行为$15$个时间片

$run\ 11$:调度系统调度任务，并运行$11$个时间片。选择任务运行$11$个时间片。任务$1$还未完成。

$add\ 2\ 0\ 6$:添加任务$2$，优先级$0$，运行为$6$个时间片。

$run3$:调度系统调度任务，因为任务$2$优先级高于任务$1$、选择任务$2$运行$3$个时间片，任务$2$未完成。

任务$2$未完成，因此显示$2$