刷题笔记合集🔗

任务调度

问题描述

小柯是一个系统管理员，负责管理一个 CPU 的任务调度。现有一系列任务需要处理，每个任务都有自己的任务 ID、优先级、所需执行时间和到达时间。CPU 同时只能运行一个任务，请编写一个任务调度程序，采用"可抢占优先权调度"调度算法进行任务调度，规则如下：

• 如果一个任务到来时，CPU 是空闲的，则 CPU 可以运行该任务直到任务执行完毕。但是如果运行中有一个更高优先级的任务到来，则 CPU 必须暂停当前任务去运行这个优先级更高的任务；
• 如果一个任务到来时，CPU 正在运行一个比它优先级更高的任务时，新到达的任务必须等待；
• 当 CPU 空闲时，如果还有任务在等待，CPU 会从这些任务中选择一个优先级最高的任务执行，相同优先级的任务选择到达时间最早的任务。

输入格式

输入有若干行，每一行有四个数字（均小于 ），分别为任务 ID，任务优先级，执行时间和到达时间。

每个任务的任务 ID 不同，优先级数字越大优先级越高，并且相同优先级的任务不会同时到达。

输入的任务已按照到达时间从小到大排序，并且保证在任何时间，处于等待的任务不超过 个。

输出格式

按照任务执行结束的顺序，输出每个任务的任务 ID 和对应的结束时间。

样例输入

1 3 5 1
2 1 5 10
3 2 7 12
4 3 2 20
5 4 9 21
6 4 2 22

样例输出

1 6
3 19
5 30
6 32
4 33
2 35

数据范围

• 任务数量不定，但每个任务的四个数字均小于
• 在任何时间，处于等待的任务不超过 个

题解

这道题考察的是操作系统中经典的"可抢占优先级调度"算法，也是优先队列在实际应用中的一个典型例子。

解题思路其实很清晰，就是模拟CPU的任务调度过程：

1. 按到达时间顺序处理每个任务
2. 对于正在执行的任务，当有新任务到达时，比较优先级决定是否抢占
3. 当CPU空闲时，从等待队列中选择优先级最高的任务执行

难点在于对各种情况的处理：

• 任务抢占后，需要记录被抢占任务的剩余执行时间
• CPU空闲期间的任务调度
• 多个优先级相同的任务处理（按到达时间排序）

实现上，核心数据结构是"优先队列"，用来维护等待执行的任务。优先队列按照任务优先级排序，优先级相同时按到达时间排序。

解题步骤：

1. 初始化一个优先队列，并将第一个任务加入队列
2. 维护当前时间curTime，初始为第一个任务的到达时间
3. 遍历所有任务，对于每个新到达的任务：
   • 如果当前任务能在新任务到达前完成，则完成当前任务，更新时间
   • 否则，更新当前任务的剩余时间，将时间推进到新任务到达时间
   • 比较新任务和当前执行任务的优先级，决定是否抢占
4. 当所有任务都加入队列后，按优先级顺序依次执行剩余任务

时间复杂度主要取决于优先队列操作，对于n个任务，每个任务最多入队出队各一次，复杂度为O(n log n)。在最坏情况下，我们可能需要维护10000个等待任务，但这对现代计算机来说完全可以接受。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()
import heapq

# 定义Task类存储任务信息
class Task:
    def __init__(self, id, priority, time, arrival):
        self.id = id            # 任务ID
        self.priority = priority # 优先级
        self.time = time        # 执行时间
        self.arrival = arrival  # 到达时间
    
    # 定义比较方法用于优先队列
    def __lt__(self, other):
        # 优先级高的在前，优先级相同则到达时间早的在前
        if self.priority != other.priority:
            return self.priority > other.priority
        return self.arrival < other.arrival

def schedule_tasks():
    tasks = []
    
    # 读取输入
    while True:
        try:
            line = input()
            if not line.strip():
                break
            task_id, priority, exec_time, arrival = map(int, line.split())
            tasks.append(Task(task_id, priority, exec_time, arrival))
        except EOFError:
            break
    
    # 如果没有任务，直接返回
    if not tasks:
        return
    
    # 初始化优先队列和当前时间
    pq = []
    heapq.heappush(pq, tasks[0])
    cur_time = tasks[0].arrival
    
    task_idx = 1  # 下一个要处理的任务索引
    
    # 处理所有任务
    while task_idx < len(tasks):
        # 当前正在执行的任务
        curr_task = pq[0]
        # 下一个到达的任务
        next_task = tasks[task_idx]
        
        # 计算当前任务的理论结束时间
        end_time = cur_time + curr_task.time
        
        # 如果当前任务能在下一个任务到达前完成
        if end_time <= next_task.arrival:
            # 移除当前任务并输出结果
            heapq.heappop(pq)
            print(f"{curr_task.id} {end_time}")
            cur_time = end_time
            
            # 处理CPU空闲期间的任务
            while pq and task_idx < len(tasks):
                idle_task = pq[0]
                idle_end = cur_time + idle_task.time
                
                # 如果任务能在下一个到达前完成
                if idle_end <= next_task.arrival:
                    heapq.heappop(pq)
                    print(f"{idle_task.id} {idle_end}")
                    cur_time = idle_end
                else:
                    # 更新剩余执行时间
                    idle_task.time -= (next_task.arrival - cur_time)
                    cur_time = next_task.arrival
                    break
                    
            # 如果队列为空，直接跳到下一个任务到达时间
            if not pq:
                cur_time = next_task.arrival
        else:
            # 当前任务无法在下一个任务到达前完成
            curr_task.time -= (next_task.arrival - cur_time)
            cur_time = next_task.arrival
        
        # 添加下一个任务到队列
        heapq.heappush(pq, next_task)
        task_idx += 1
    
    # 处理剩余的任务
    while pq: