java - 找到尽可能多的对

Question

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

任务:

聚会上有 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

第一行是 guest 人数，后面的数据是参加聚会的人的间隔。

Answer 1

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

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