4

我正在尝试解决一个问题，但不幸的是我的解决方案对于这项任务来说并不是最好的。

任务：

在一次聚会上，有 N 位客人（0 < N < 30000）。所有客人都告知他们何时参加派对以及何时离开（例如 [10;12]）。任务是在聚会上为尽可能多的人拍照。在一张照片上只能有 2 个人（一对），每个人只能在一张照片上。当然，只有在两个人同时在聚会时才能拍照。当他们的出勤间隔重叠时就是这种情况。

我的想法：我写了一个程序，它从间隔创建一个连接图。从图中我搜索连接数最少的人。从关联的人中，我还选择了关联最少的人。然后这两个被选为照片上的一对。两者都从图中删除。该算法一直运行到没有连接为止。

这种方法有效，但是程序计算有 10 秒的限制。如果有 1000 个条目，它会在 2 秒内运行，但即使有 4000 个条目，它也需要很长时间。此外，当我尝试使用 25000 个数据时，程序因内存不足错误而停止，因此我什至无法正确存储连接。

我认为这里需要一种新方法，但我找不到其他方法来完成这项工作。

谁能帮我找出适合这项任务的算法？

非常感谢你！

样本数据：

10
1 100
2 92
3 83
4 74
5 65
6 55
7 44
8 33
9 22
10 11

第一行是客人的数量，进一步的数据是参加聚会的人的间隔。

4

6 回答 6

3

这里不需要创建图，这个问题可以在区间结构上很好地解决。按离开时间的升序（间隔结束点）对人员进行排序。然后按排序顺序遍历它们：如果当前人没有与任何人相交，那么他应该被删除。如果他与多个人相交，则以离开时间最早的人为一组。在迭代期间，您应该只将每个人与下一个人进行比较。

证明这种方法并不难，所以希望你能自己证明。关于运行时间，简单的解决方案是 O(N^2)，但我认为它可以减少到 O(N * logN)。无论如何，O(N^2) 将适合普通 PC 上的 10 秒。

于 2013-03-07T10:26:46.980 回答
2

对我来说，这似乎是一个经典的最大匹配问题。

您构建一个图，其中可能被描绘在一起的人（他们的时间间隔相交）与一条边相连，然后找到最大匹配，例如，使用 Edmond 的 Blossom 算法。

我不会说，这很容易实现。但是，您可以使用Kuhn 算法在二分图中获得最大匹配的相当好的近似值。这个很容易实现，但不会给你确切的解决方案。

于 2013-03-07T09:34:27.083 回答
1

我有一些非常简单的想法：

假设，派对将占用 Xh，每小时制作 X 组，添加合适的人。当然，在那里待的时间超过一小时的人会在几组中。现在，如果有 2 套“一起”，偶数个 ppl，你可以为每套拍摄 n/2 张照片。如果有 2 组奇数人，您正在寻找将在这 2 组中的每一组的人，并将他移动到其中一组（所以您有 2 组偶数组的人将同时在派对）。

请记住删除所有使用过的 ppl（考虑一些class-Man列出他/她的所有时间）。

我的想法可能应该扩展到更高级的“移动人”算法，通过多个相邻集。

于 2013-03-07T09:28:35.590 回答
1

我认为以下可以做到：

首先，读取所有客人的数据，并将它们按时间升序排列成一个数组。然后，获取数组的第一个元素并遍历下一个元素，直到找到第一个时间匹配（下一个客人的进入时间小于该客人的离开时间），如果找到，则将两者作为一对从数组中删除，并在其他地方报告. 如果没有，请移除客人，因为它根本无法配对。重复直到数组为空。

最坏的情况也是 N^2，因为聚会就像[1,2],[3,4],...没有客人可以配对，算法会一直搜索所有 30000 名客人都是徒劳的。所以我不认为这是最佳算法，但它应该给出一个准确的答案。

于 2013-03-07T11:33:56.890 回答
0

你说你已经有了一个图结构表示。我假设您的顶点代表客人和他们在聚会上的时间间隔，而边缘代表各自时间间隔的重叠。那么你要解决的是图论最大匹配问题，这个问题之前已经解决了。

然而，正如我在上面的评论中所指出的，我认为你可以利用问题的性质，尤其是传递性，比如“如果 A 在 B 离开之前离开，B 在 C 到达之前离开，那么 A 和 C 也不会相遇”，比如这：

等到下一位未拍照的客人即将离开，然后与在场的下一位离开的客人合影留念。

于 2013-03-07T09:35:25.847 回答
-1

您可能会成功地想到可以拍摄照片的最早时间：这是第二个人到达聚会的时间。

所以作为一名摄影师，以第一个人的身份参加派对并等待。每当有人到达时，请与他/她以及聚会上的所有其他人合影。由于一个人只出现一次，因此您不会有任何重复。

在拍照时（即遍历客人列表），删除那些实际离开聚会的客人。

于 2013-03-07T08:59:27.257 回答