解题思路

我们有 M 台服务器（编号 1..M），N 个任务（编号 1..N）。第 i 个任务给出启动时间 s_i 与执行时间 t_i，不同任务的启动时间两两不同。任务按启动时间发生： 当某任务到来时，所有在该时刻之前或恰好完成的任务会释放其服务器；若有空闲服务器，则该任务立刻占用编号最小的空闲服务器并执行。要求输出编号为 K 的任务在执行时占用的服务器编号。

核心算法：事件模拟 + 两个小根堆（优先队列）

1. 将任务按启动时间 s_i 升序排序，同时保留任务原编号 i。

2. 维护两个堆：

   • avail：空闲服务器编号的小根堆（初始放入 1..M）。
   • busy：正在运行任务的小根堆，元素为 (结束时间, 服务器编号)。

3. 依次处理每个任务 (s_i, t_i, i)：

   • 先把 busy 中所有 结束时间 <= s_i 的元素弹出，并把对应服务器放回 avail；
   • 从 avail 弹出最小编号的服务器 id，记录 ans[i] = id；
   • 将 (s_i + t_i, id) 压入 busy。

4. 最后输出 ans[K]。

复杂度分析

• 排序：O(N log N)
• 每个任务最多一次入堆/出堆，两类堆的操作均为 O(log M)，合计 O(N log M)
• 总时间复杂度：O(N log N + N log M)
• 空间复杂度：O(M + N)（两个堆与答案数组）

代码实现

Python

import sys
import heapq

def server_of_k(M, tasks, K):
    # tasks: 列表 [(s, t, idx)]
    tasks.sort(key=lambda x: x[0])  # 按启动时间排序

    # 空闲服务器小根堆（编号最小优先）
    avail = list(range(1, M + 1))
    heapq.heapify(avail)

    # 正在运行的任务：(结束时间, 服务器编号)
    busy = []

    # 记录每个原编号任务的分配服务器
    ans = [0] * (len(tasks) + 1)

    for s, t, idx in tasks:
        # 释放所有在 s 之前或恰好 s 时刻完成的任务
        while busy and busy[0][0] <= s:
            end_time, sid = heapq.heappop(busy)
            heapq.heappush(avail, sid)

        # 取出最小编号的空闲服务器
        sid = heapq.heappop(avail)
        ans[idx] = sid

        # 压入该任务的结束事件
        heapq.heappush(busy, (s + t, sid))

    return ans[K]

def main():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    M = int(next(it)); N = int(next(it)); K = int(next(it))
    tasks = []
    for i in range(1, N + 1):
        s = int(next(it)); t = int(next(it))
        tasks.append((s, t, i))
    print(server_of_k(M, tasks, K))

if __name__ == "__main__":
    main()

Java

import java.util.*;

public class Main {

    static int serverOfK(int M, int[][] tasks, int K) {
        // 按启动时间升序
        Arrays.sort(tasks, Comparator.comparingInt(a -> a[0]));

        // 空闲服务器：小根堆（编号最小优先）
        PriorityQueue<Integer> avail = new PriorityQueue<>();
        for (int i = 1; i <= M; i++) avail.offer(i);

        // 正在运行：小根堆（结束时间最小优先）
        // 元素为 int[]{endTime, serverId}
        PriorityQueue<int[]> busy = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));

        int n = tasks.length;
        int[] ans = new int[n + 1]; // 以任务原编号为下标

        for (int[] x : tasks) {
            int s = x[0], t = x[1], idx = x[2];

            // 释放完成的任务（结束时间 <= 当前启动时间）
            while (!busy.isEmpty() && busy.peek()[0] <= s) {
                int[] cur = busy.poll();
                avail.offer(cur[1]);
            }

            // 分配最小编号服务器
            int sid = avail.poll();
            ans[idx] = sid;

            // 加入结束事件
            busy.offer(new int[]{s + t, sid});
        }

        return ans[K];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int M = sc.nextInt();
        int N = sc.nextInt();
        int K = sc.nextInt();

        // tasks[i] = {start, duration, originalIndex}
        int[][] tasks = new int[N][3];
        for (int i = 0; i < N; i++) {
            int s = sc.nextInt();
            int t = sc.nextInt();
            tasks[i][0] = s;
            tasks[i][1] = t;
            tasks[i][2] = i + 1; // 原编号
        }

        System.out.println(serverOfK(M, tasks, K));
    }
}

C++

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

int server_of_k(int M, vector<tuple<int,int,int>>& tasks, int K) {
    // 按启动时间排序
    sort(tasks.begin(), tasks.end());

    // 空闲服务器：最小编号优先
    priority_queue<int, vector<int>, greater<int>> avail;
    for (int i = 1; i <= M; ++i) avail.push(i);

    // 正在运行任务：结束时间最小优先，元素 (end, serverId)
    using PII = pair<int,int>;
    priority_queue<PII, vector<PII>, greater<PII>> busy;

    int n = (int)tasks.size();
    vector<int> ans(n + 1, 0); // 原编号 -> 服务器编号

    for (auto &tp : tasks) {
        int s = get<0>(tp), t = get<1>(tp), idx = get<2>(tp);

        // 释放到当前时刻已完成的任务
        while (!busy.empty() && busy.top().first <= s) {
            int sid = busy.top().second;
            busy.pop();
            avail.push(sid);
        }

        // 分配最小编号的空闲服务器
        int sid = avail.top(); avail.pop();
        ans[idx] = sid;

        // 加入结束事件
        busy.push({s + t, sid});
    }
    return ans[K];
}

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

    int M, N, K;
    if (!(cin >> M >> N >> K)) return 0;

    vector<tuple<int,int,int>> tasks;
    tasks.reserve(N);
    for (int i = 0; i < N; ++i) {
        int s, t;
        cin >> s >> t;
        tasks.emplace_back(s, t, i + 1); // 保存原编号
    }

    cout << server_of_k(M, tasks, K) << "\n";
    return 0;
}

题目内容

数据中心有 $M$ 个服务器(编号 $1-M$ )，现在 $N$ 个(编号 $1-N$ )需要执行，当一个任务开始执行时，会独占编号最小的空闲服务器，执行完后会立即释放该服多器。任务按照启动时间的先后顺序执行(所有任务的启动时间都不相同)。请返回编号为 $K$ 的任务执行时占用的服务器编号。

输入描述

第一行是用空格分隔的三个整数：$M，N，K$ 分别代表服务器个数，任务数，需要查询的任务编号， $1<=K<=N <= M <= 10^4$

接下来 $N$ 行是编号 $1-N$ 的任务信息，每行是用空格分隔的两个整数，分别代表任务的启动时间，执行需要的时间。$1<=$ 启动时间，执行时间 $<=10^5$

输出描述

编号为 $K$ 的任务执行时占用的服务器编号

样例1

输入

4 3 2
1 2
4 6
3 3

输出

2

说明

编号为 $1$ 的任务(启动时间为 $1$ )占用 $1$ 号服务器

编号为 $3$ 的任务(启动时间为 $3$ )执行时，编号为 $1$ 的任务已经执行完，$1$ 号服务器空闲，所以占用 $1$ 号服务器

编号为 $2$ 的任务(启动时间为 $4$ )执行时，编号为 $3$ 的任务还没有执行完，所以占用 $2$ 号服务器

样例2

输入

2 1 1
1 5

输出

1

说明

只有 $1$ 个任务，占用 $1$ 号服务器