题解 | #任务调度#

python 双堆

import heapq

n,m,p = map(int,input().split())

idea = [[] for _ in range(3005)]
for i in range(p):
    a,b,c,d = map(int,input().split())
    t = [c,d,b,d,a,i]  # 题目要求的优先级顺序
    idea[b].append(t)

h1,h2 = [],[]  # h1是程序员，h2是任务堆
ans = [0]*p
for i in range(3005):
    # 释放已经结束的程序员
    while h1 and h1[0]<=i:
        heapq.heappop(h1)
    # 处理当前任务堆中的元素
    for x in idea[i]:
        heapq.heappush(h2, x)
    left = m-len(h1)
    while left>0 and h2:
        t = heapq.heappop(h2)
        heapq.heappush(h1,i+t[-3])
        ans[t[-1]] = i+t[-3]
        left = m-len(h1)
for i in range(3005,6005):
    while h1 and h1[0]<=i:
        heapq.heappop(h1)
    left = m-len(h1)
    while left>0 and h2:
        t = heapq.heappop(h2)
        heapq.heappush(h1,i+t[-3])
        ans[t[-1]] = i+t[-3]
        left = m-len(h1)
    if not h2:
        break



for x in ans:
    print(x)