首页 > 试题广场 >

任务调度

[编程题]任务调度

热度指数：1417 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

产品经理(PM)有很多好的idea，而这些idea需要程序员实现。现在有N个PM，在某个时间会想出一个 idea，每个 idea 有提出时间、所需时间和优先等级。对于一个PM来说，最想实现的idea首先考虑优先等级高的，相同的情况下优先所需时间最小的，还相同的情况下选择最早想出的，没有 PM会在同一时刻提出两个 idea。

同时有M个程序员，每个程序员空闲的时候就会查看每个PM尚未执行并且最想完成的一个idea,然后从中挑选出所需时间最小的一个idea独立实现，如果所需时间相同则选择PM序号最小的。直到完成了idea才会重复上述操作。如果有多个同时处于空闲状态的程序员，那么他们会依次进行查看idea的操作。

求每个idea实现的时间。

输入描述:

输入第一行三个数N、M、P，分别表示有N个PM，M个程序员，P个idea。随后有P行，每行有4个数字，分别是PM序号、提出时间、优先等级和所需时间。

所有输入数据范围为 [1, 3000]

输出描述:

输出P行，分别表示每个idea实现的时间点。

示例1

输入

输出

算法知识视频讲解

Python

名柳字思牧

勉强跑通，完全用的模拟法，所以很好奇，动态规划怎么个规划法。

N,M,P = [int(a) for a in input().split()]
Ideas = {}
for i in range(P):
    X = [int(a) for a in input().split()]
    Ideas[X[0]] = Ideas.get(X[0],[]) + [[i]+X[1:]]
for k,v in Ideas.items():
    v.sort(key=lambda x:(-x[2],x[3],x[1]))
    Ideas[k]=v

def Select(t):
    a,b,c = 0,0,9999
    for k in Ideas.keys():
        for j in range(len(Ideas[k])):
            if Ideas[k][j][1]<=t:
                if Ideas[k][j][3]<c&nbs***bsp;(Ideas[k][j][3]==c and k<a):
                    a,b,c = k,j,Ideas[k][j][3]
                break
    idx = -1
    if a>0:
        idx = Ideas[a][b][0]
        Ideas[a] = Ideas[a][:b]+Ideas[a][b+1:]
    return idx,c

result = [0]*P
CXY = [0]*M
t,count = 1,0
while count<P:
    flag = 0
    for i in range(M):
        if CXY[i]==0:
            idx,c = Select(t)
            if idx<0:
                flag=1
                break
            result[idx] = t+c
            CXY[i]=c
            count += 1
    if flag>0:
        t += 1
        CXY = [c-1 if c>0 else 0 for c in CXY]
    else:
        m = min(CXY)
        t += m
        CXY = [c-m for x in CXY]
for r in result:
    print(r)

编辑于 2021-03-15 20:16:07 回复(0)