2

我有很多间隔（x，y），我想将它们组合在一起。规则是，如果一组区间都嵌套在组的一个成员中，则一组区间属于同一组，除了一个是它们都嵌套在其中的最大区间。例如，(1,7), (2, 4),(2,9), (8,9) 可以分为两组 (1,7),(2,4) 和 (2,9),(8,9)。当然，这不是唯一的，但它是最小的，因为您不能拥有更少的组。

为了使它更复杂，我无法一次读取所有数据，因为它太大了。

例如，我可以按每对中的第一个元素对数据进行离线排序。

什么是解决这个问题的好算法？

4

4 回答 4

2

通过不减少 x 对区间进行排序，通过不增加 y 来打破平局。按顺序扫描间隔。虽然存在更多间隔，但将第一个保留为新组的封闭间隔，并尽可能将每个连续的间隔添加到组中。

假设存在两个区间 [x, y] 和 [x', y'] 使得 x <= x' <= y' <= y。然后我们可以证明 [x', y'] 不是一个群的封闭区间，因此分组是最小的。如果 [x, y] = [x', y']，那么很明显 [x, y] 和 [x', y'] 被分配到同一个组。否则，区间 [x, y] 排在 [x', y'] 之前，因为 x < x' 或 x = x' 且 y' < y。扫描 [x', y'] 时激活的封闭区间 [x'', y''] 满足 x'' <= x' （按排序顺序）和 y' <= y <= y'' （因为活动封闭区间的 y 坐标不随时间递减）。因此，[x', y'] 不会开始一个组。

于 2013-07-18T22:03:30.983 回答
0

按 xy 最大优先（离线）的大小对输入组进行排序。

查看组列表并检查每个组是否包含在它之前的组中。如果是 - 从列表中删除它并在文件中标记（文件说明很快）如果不是 - 它是一个组

文件：保留根据输入列表中组的索引命名的文件结构。随时创建文件，并在任何文件中保留所有 (x,y) 对。

这会给你一个相对好的答案，但我不确定它是否是最佳答案。

时间：

  • 排序 = o(nlogn)
  • 在最坏的情况下（如果没有组相交），通过列表最多可以达到 o(n^2)
于 2013-07-17T18:55:33.433 回答
0

这可能很简单，但基于您给出的假设应该是适当的。假设输入数据是一个无穷无尽的未知流/队列

  1. 从队列中取出项目。
  2. 如果第一个创建新组。
  3. 如果不是第一个遍历现有组并放入第一个匹配组。
  4. 如果不能放入任何组创建新组
  5. 重复这个过程

您可以在此处应用其他限制（最大组大小等）

于 2013-07-17T18:55:57.300 回答
0

这个怎么样：

  1. 使用范围开始（第一个元素）对间隔进行排序。

  2. 从排序集中取第一个间隔。记住它。添加到列表中。

  3. while（拿下一个）

        a. it can be fully inclusive in any of the elements in the list, add it to the group of contained interval.
    b. Partial inclusive, add a new member in memory. append it to the list.
    c. totally Exclusive, add it to the list, remove previous elements in the list and persist in disk.
于 2013-07-17T19:02:45.867 回答