2

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

简要问题说明：
有一组“作业”（任务）应该在多个“服务器”（计算机）上执行。
每个作业都应该从开始时间 S i到结束时间 E i
严格执行 每个服务器一次只能执行一个任务。
（复杂的事情在这里）服务器从一个工作切换到另一个工作需要一些时间。
如果服务器完成作业 J x，那么要启动作业 J y，它将需要在作业 J x完成后的间歇时间 T x,y 。这是服务器清理作业 J x和加载作业 J y所需的时间。 换句话说，工作 J y
当且仅当 E x + T x,y ≤ S y时，才能在作业 J x之后运行。

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

示例：
例如，假设有 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 个作业），然后是 E i和 S i，然后是 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

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

4

1 回答 1

3

您可以通过计算二分图中的最大匹配来解决此问题。

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

结束时间 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')
于 2013-10-18T17:54:46.973 回答