algorithm - 需要帮助解决编程竞赛中的问题

Question

关闭。这个问题不满足Stack Overflow guidelines .它目前不接受答案。












想改善这个问题吗？更新问题，使其成为 on-topic对于堆栈溢出。

7年前关闭。



Improve this question




我参加了我所在国家/地区的本地编程比赛。比赛名称为“ACM-ICPC Indonesia National Contest 2013”​​。
比赛已于2013-10-13 15:00:00(GMT +7)结束，我仍然对其中一个问题感到好奇。
您可以找到问题的原始版本here .

简要问题说明:
有一组“作业”(任务)应该在多个“服务器”(计算机)上执行。
每个作业从开始时间 Si 到结束时间 Ei 都应该严格执行
每个服务器一次只能执行一项任务。
(复杂的事情就到这里了)服务器从一项工作切换到另一项工作需要一些时间。
如果服务器完成了作业 Jx，那么要启 Action 业 Jy，它在作业 Jx 完成后需要一个间歇时间 Tx,y。这是服务器清理作业 Jx 和加载作业 Jy 所需的时间。
换句话说，当且仅当 Ex + Tx,y ≤ Sy 时，作业 Jy 可以在作业 Jx 之后运行。

问题是计算完成所有作业所需的最少服务器数量。

示例:
例如，假设有 3 个工作

S(1) =  3 and E(1) =  6
S(2) = 10 and E(2) = 15
S(3) = 16 and E(3) = 20
T(1,2) = 2,  T(1,3) = 5
T(2,1) = 0,  T(2,3) = 3
T(3,1) = 0,  T(3,2) = 0

在这个例子中，我们需要 2 个服务器:

Server 1: J(1), J(2)
Server 2: J(3)

样本输入:
简短说明:第一个 3是测试用例的数量，接下来是作业数量(第二个 3 表示案例 1 有 3 个作业)，然后是 Ei 和 Si，然后是 T 矩阵(大小等于作业数量)。

3
3
3 6
10 15
16 20
0 2 5
0 0 3
0 0 0
4
8 10
4 7
12 15
1 4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
4
8 10
4 7
12 15
1 4
0 50 50 50
50 0 50 50
50 50 0 50
50 50 50 0

示例输出:

案例#1:2
案例#2:1
案例#3:4

个人评论:
所需的时间可以表示为图矩阵，所以我假设这是一个有向无环图问题。
到目前为止我尝试过的方法是蛮力和贪婪，但得到了错误的答案。 (不幸的是我没有我的代码了)
也可以通过动态编程解决，但我不确定。
我真的不知道如何解决这个问题。
因此，一个简单的提示或见解对我非常有帮助。

Answer 1

您可以通过计算 maximum matching in a bipartite graph 来解决这个问题。 .

这个想法是你试图将工作结束时间与工作开始时间相匹配。

结束时间 x 与开始时间 y 匹配意味着同一台服务器将执行作业 x 和作业 y。

您需要的服务器数量将对应于不匹配的开始时间的数量(因为这些作业中的每一个都需要一个新服务器)。

使用 NetworkX 的 Python 代码示例:

import networkx as nx
G=nx.DiGraph()

S=[3,10,16] # start times
E=[6,15,20] # end times
T = [ [0, 2, 5],
      [0, 0, 3],
      [0, 0, 0] ] # T[x][y]
N=len(S)

for jobx in range(N):
    G.add_edge('start','end'+str(jobx),capacity=1)
    G.add_edge('start'+str(jobx),'end',capacity=1)
    for joby in range(N):
        if E[jobx]+T[jobx][joby] <= S[joby]:
            G.add_edge('end'+str(jobx),'start'+str(joby),capacity=1)

print N-nx.max_flow(G,'start','end')