algorithm - 开始和结束时间为 "consolidate overlap"的最有效方法

Question

假设我们有一个数据结构:

class Segment{
    float startTime;
    float endTime;
}

我们有一堆片段，其中一些具有重叠的持续时间。合并这些段以使其具有不重叠持续时间的最佳方法是什么？

Answer 1

一个选项是创建一个包含所有开始时间和结束时间的数组，然后将其按时间顺序排序。然后您可以从左到右遍历数组，在每个点跟踪开放间隔的数量。每当看到开始时间，就增加间隔数，每当看到结束时间，就减少间隔数。当您执行此操作时，无论何时从零开放间隔变为一，记录新间隔的开始，每当您从一个开放间隔变为零，记录关闭时间。

总的来说，这个运行时间为 O(sort + n)。如果您使用堆排序或快速排序之类的方法，则时间为 O(n log n)。如果您使用基数排序之类的东西 - 假设它适用 - 这将是时间 O(n log U)，其中 U 是最大值。

希望这对您有所帮助!