-1

我正在阅读一个对我来说似乎是分配问题的问题。这是摘要：一家公司有 N 个工作。N 个候选人来申请它，但在不同的时间。

给定一个 NxN 矩阵，其中单元格 (i,j) 表示求职者 i 接近第 j 个公司的时间。您必须找到有效的一对一作业。如果将工作分配给候选人，则该候选人不会寻找更多工作。没有两个候选人必须获得相同的工作。此外，在任何给定时刻，不得有两个候选人在同一个工作办公室。输出应该是任何一个排列满足上述约束。

例如：输入：

1 2 3

4 5 6

7 8 9

输出：

3 2 1

解释：在时间=1秒，第一个候选人去第一份工作。然后在时间=2秒，去第二份工作。但他最终在时间3被分配了工作3。然后在第5秒，工作2将被分配给第二份工作。所以他不会在时间=6时去工作3。那么最后第1个工作将在t=7时分配给第3个cand。

请注意，任何其他排列都是不正确的。对于输出 (1 2 3) 将是错误的，因为第一个候选人将被分配第一个工作。所以他不会寻找工作 2 和 3。但是在 4 秒时，第二个候选人会也申请已经有第一人在办公室的第一份工作。

我的问题是如何处理此类分配问题？

4

2 回答 2

0

这是目前正在进行的 CodeChef 八月挑战编程竞赛的 BLOCKING 问题。在比赛进行时要求这些提示是违反规则的。

http://www.codechef.com/AUG12/problems/BLOCKING

周末比赛结束后，您将能够通过查看其他竞争对手的答案来获得答案。

于 2012-08-07T23:54:29.003 回答
0

如果您按时间排序（i，j），那么现在哪个人最后申请了工作，给那个人那个工作。仍然会有人在更早的时间从事所有其他工作（因为否则它不会是最长时间）。现在继续重复这个，你会很快得到一个作业：

matrix = [[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]

dictionary = {}
for person in range(3):
    for job in range(3):
        time = matrix[person][job]
        dictionary[time] = (person, job)

ordered_time = sorted(dictionary.keys(), reverse=True)

taken_job = set()
taken_person = set()
assignment = []
for time in ordered_time:
    person, job = dictionary[time]
    if person not in taken_person and job not in taken_job:
        assignment.append("t=%s, i=%s, j=%s" % (time, person, job))
        taken_job.add(job)
        taken_person.add(person)

print(assignment)
#['t=9, i=2, j=2', 't=5, i=1, j=1', 't=1, i=0, j=0']
于 2012-08-05T22:37:09.433 回答