自上而下合并范围？

Question

我想要像这样合并一些区间：

>>> ranges = [(30, 45), (40, 50), (10, 50), (60, 90), (90, 100)]
>>> merge(ranges)
[(10, 50), (60, 100)]

我不是计算机科学相关专业的人。我知道可以通过迭代方法合并这些数据，但是想知道是否有更高效的“自顶向下”的方法可以使用一些特殊的数据结构使其更加高效？

谢谢。

- Jingping

Answer 1

间隔树肯定是有效的，但它比你需要的更加复杂。间隔树是一种“在线”解决方案，因此它允许您添加一些间隔，查看并集，再添加更多间隔，再次查看等等。

如果您提前拥有所有区间，您可以做一些更简单的事情：

1. 从输入开始 ranges = [(30, 45), (40, 50), (10, 50)] 2. 将区间列表转换为端点列表。如果您有范围（A，B），则将其转换为两个端点：左端点为（A，0）和右端点为（B，1）。 endpoints = [(30, 0)，(45, 1)，(40, 0)，(50, 1)，(10, 0)，(50, 1)] 3. 对端点进行排序 endpoints = [(10, 0)，(30, 0)，(40, 0)，(45, 1)，(50, 1)，(50, 1)] 4. 正向扫描端点列表。当您看到左端点时，增加计数器；当您看到右端点时，减少计数器。每当计数器达到0时，关闭当前合并间隔。

这个解决方案可以用几行代码实现。

- Igor ostrovsky

---

如果有多个重叠区间的集群，这会起作用吗？ - Jingping

我真的很喜欢这个优雅的想法 :) - Jingping

是的，它可以在任意数量的群集中运行。每次计数器归零时，您已经到达了合并群集的末尾。下一个端点必须是左端点（否则您的数据将被搞乱），并且它将开始下一个合并群集。 - Igor ostrovsky

我现在明白了，尽管我认为这应该与排序和成对合并方法具有类似的时间复杂度，是吗？ - Jingping

真的 - 你可以根据左端点对区间进行排序，然后向前迭代，如果它们重叠，则合并区间。老实说，我没有想到这种方法 :) - Igor ostrovsky

Answer 2

是的，高效的方法是使用区间树。

- jason

---

嗨，Jason，我刚查了一下区间树，并且大致明白了基本概念。但是我对如何使用它来合并区间感到困惑，请您给我介绍一下这里缺失的环节。谢谢。 - Jingping

我所能想到的唯一方法就是构建区间树，然后对这些区间进行排序，并将最左侧的区间作为第一个查询。在树中搜索并获取所有相交的区间，然后合并它们，并迭代执行此操作，直到合并范围不再改变；然后使用下一个右侧区间开始第二轮扫描。这是扫描整个树以获取所有重叠区间的“子树”的正确方法吗？ - Jingping

Answer 3

以下是使用C#编写的算法，它可以实现您想要的功能。它使用DateTime间隔范围，但您可以根据需要进行调整。一旦集合按升序开始排序，如果下一个间隔的开始时间在前一个间隔的结束时间之前或同时，它们就会重叠，并且如果需要，您可以向外扩展结束时间。否则，它们不重叠，您可以将前一个间隔保存到结果中。

public static List<DateTimeRange> MergeTimeRanges(List<DateTimeRange> inputRanges)
{
  List<DateTimeRange> mergedRanges = new List<DateTimeRange>();

  // Sort in ascending start order.
  inputRanges.Sort();

  DateTime currentStart = inputRanges[0].Start;
  DateTime currentEnd = inputRanges[0].End;

  for (int i = 1; i < inputRanges.Count; i++)
  {
    if (inputRanges[i].Start <= currentEnd)
    {
      if (inputRanges[i].End > currentEnd)
      {
        currentEnd = inputRanges[i].End; // Extend range.
      }
    }
    else
    {
      // Save current range to output.
      mergedRanges.Add(new DateTimeRange(currentStart, currentEnd));

      currentStart = inputRanges[i].Start;
      currentEnd = inputRanges[i].End;
    }
  }

  mergedRanges.Add(new DateTimeRange(currentStart, currentEnd));

  return mergedRanges;
}

- Pete Rihaczek