题面描述

团队申请了一组服务器，用于机器学习训练。为了充分利用资源，需要实现一个任务调度算法。具体要求如下：

• 服务器与任务：

  • 有 $M$ 台空闲服务器。
  • 有 $N$ 个训练任务，每个任务有训练时间 $T$ 和优先级 $P$。

• 调度规则：

  • 每台服务器同一时间只能执行一个训练任务。
  • 所有任务在开始时刻（零时刻）一次性提交完毕，等待调度。
  • 任务一旦开始执行，就不能暂停或更换服务器，直到任务结束。
  • 优先级调度：
    • 当空闲服务器不足时，优先执行优先级高（$P$ 值小）的训练任务。
    • 如果多个训练任务的优先级相同，优先执行训练时间长的任务。
    • 当空闲服务器充足时，可以同时执行不同优先级的训练任务。

• 目标：

  • 计算完成所有训练任务的总时间。

思路

为了计算完成所有训练任务的最小总时间，可以采用以下步骤：

1. 任务排序：

   • 首先，根据优先级 $P$ 升序排序任务（即优先级高的任务排在前面）。
   • 对于优先级相同的任务，按照训练时间 $T$ 降序排序（即训练时间长的任务排在前面）。

2. 服务器调度：

   • 使用一个最小堆（优先队列）来跟踪每台服务器的空闲时间。初始时，所有服务器的空闲时间为 $0$。
   • 遍历排序后的任务列表，对于每个任务：
     • 从堆中取出当前最早空闲的服务器的空闲时间。
     • 该任务的开始时间为服务器的空闲时间。
     • 更新服务器的空闲时间为 开始时间 + T。
     • 将更新后的空闲时间重新放回堆中。
     • 记录任务的结束时间，维护一个最大结束时间作为总时间。

3. 结果输出：

   • 遍历完所有任务后，最大结束时间即为完成所有任务的总时间。

这种方法的时间复杂度为 $O(N \log N + N \log M)$，其中 $N$ 是任务数量，$M$ 是服务器数量。在题目给定的约束下，该算法是可行且高效的。

cpp

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

struct Task {
    int T;
    int P;
};

// Comparator: 优先级升序，训练时间降序
bool cmp(const Task &a, const Task &b) {
    if(a.P != b.P)
        return a.P < b.P;
    return a.T > b.T;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int M, N;
    cin >> M >> N;
    vector<Task> tasks(N);
    for(int i=0; i<N; ++i){
        cin >> tasks[i].T >> tasks[i].P;
    }
    // 排序
    sort(tasks.begin(), tasks.end(), cmp);
    // 最小堆，存储服务器的空闲时间
    priority_queue<long long, vector<long long>, std::greater<long long>> pq;
    // 初始化所有服务器为空闲，时间为0
    for(int i=0; i<M; ++i){
        pq.push(0);
    }
    long long max_time = 0;
    for(auto &task: tasks){
        long long avail_time = pq.top(); pq.pop();
        long long finish_time = avail_time + task.T;
        max_time = max(max_time, finish_time);
        pq.push(finish_time);
    }
    cout << max_time;
}

python

import sys
import heapq


def main():
    import sys
    import sys
    input = sys.stdin.read
    data = input().split()

    idx = 0
    M = int(data[idx]);
    idx += 1
    N = int(data[idx]);
    idx += 1
    tasks = []
    for _ in range(N):
        T = int(data[idx]);
        idx += 1
        P = int(data[idx]);
        idx += 1
        tasks.append((P, -T))  # 负的T用于降序排序

    # 排序：优先级升序，训练时间降序
    tasks.sort()

    # 初始化最小堆，存储每台服务器的空闲时间
    heap = [0] * M
    heapq.heapify(heap)

    max_time = 0
    for P, neg_T in tasks:
        T = -neg_T
        avail_time = heapq.heappop(heap)
        finish_time = avail_time + T
        max_time = max(max_time, finish_time)
        heapq.heappush(heap, finish_time)

    print(max_time)


if __name__ == "__main__":
    main()

java

import java.util.*;

public class Main {
    static class Task {
        int time; // 训练时间
        int priority; // 优先级
        
        Task(int time, int priority) {
            this.time = time;
            this.priority = priority;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取服务器数量和任务数量
        int M = scanner.nextInt(); // 空闲服务器的数量
        int N = scanner.nextInt(); // 训练任务的数量
        
        List<Task> tasks = new ArrayList<>();
        
        // 读取任务信息
        for (int i = 0; i < N; i++) {
            int T = scanner.nextInt(); // 训练时间
            int P = scanner.nextInt(); // 优先级
            tasks.add(new Task(T, P));
        }
        
        // 按优先级升序、训练时间降序排序
        tasks.sort((a, b) -> {
            if (a.priority != b.priority) {
                return Integer.compare(a.priority, b.priority); // 优先级比较
            }
            return Integer.compare(b.time, a.time); // 训练时间比较
        });
        
        // 初始化最小堆，存储每台服务器的空闲时间
        PriorityQueue<Long> minHeap = new PriorityQueue<>();
        for (int i = 0; i < M; i++) {
            minHeap.offer(0L); // 初始时，所有服务器的空闲时间为0
        }
        
        long maxTime = 0; // 记录最大完成时间
        
        // 处理所有任务
        for (Task task : tasks) {
            long availTime = minHeap.poll(); // 取出最早空闲的服务器时间
            long finishTime = availTime + task.time; // 计算任务完成时间
            maxTime = Math.max(maxTime, finishTime); // 更新最大完成时间
            minHeap.offer(finishTime); // 将新的空闲时间放回堆中
        }
        
        // 输出完成所有任务的总时间
        System.out.println(maxTime);
    }
}