我们有 M 台服务器(编号 1..M),N 个任务(编号 1..N)。第 i 个任务给出启动时间 s_i 与执行时间 t_i,不同任务的启动时间两两不同。任务按启动时间发生:
当某任务到来时,所有在该时刻之前或恰好完成的任务会释放其服务器;若有空闲服务器,则该任务立刻占用编号最小的空闲服务器并执行。要求输出编号为 K 的任务在执行时占用的服务器编号。
核心算法:事件模拟 + 两个小根堆(优先队列)
s_i 升序排序,同时保留任务原编号 i。数据中心有 M 个服务器(编号 1−M ),现在 N 个(编号 1−N )需要执行,当一个任务开始执行时,会独占编号最小的空闲服务器,执行完后会立即释放该服多器。任务按照启动时间的先后顺序执行(所有任务的启动时间都不相同)。请返回编号为 K 的任务执行时占用的服务器编号。
第一行是用空格分隔的三个整数:M,N,K 分别代表服务器个数,任务数,需要查询的任务编号, 1<=K<=N<=M<=104