algorithm - 在重叠区间中查找基本区间

Question

我在准备一些编程面试时遇到了一个很好的问题。

给定一组可能重叠的区间，您需要编写一个函数来返回其中的所有基本区间。例如:如果给定区间为以下对列表:{{1,5}、{3,10}、{5,11}、{15,18}、{16,20}}，那么您需要返回以下内容:

{{1,3}, {3,5}, {5,10}, {10,11}, {15,16}, {16,18}, {18,20}}

请注意上述答案中的以下内容:

• 答案中省略了区间 {11,15}，因为它是 输入中不存在。
• 输入的区间 {1,5} 已被拆分为 {1,3}、{3,5} 在答案中，因为在 {3,10} 中定义了起点“3” 将区间切割成两个基本区间的输入。

Java 中的方法签名:

List<Pair<Integer, Integer>> generateElementaryIntervals(List<Pair<Integer, Integer> intervals)

我想象的解决方案之一是将输入分成非相交集，然后对每个非相交集中的所有数字进行简单的 O(NlogN) 排序将得出答案。有没有更有效的方法呢？

Answer 1

您可以先将此问题分解为嵌套区间，然后分别处理每个嵌套。嵌套是指至少共享一个点的区间。对于您给出的示例:

{{1,5}, {3,10}, {5,11}, {15,18}, {16,20}}

有两个嵌套:

{1,5}, {3,10}, {5,11}

和

{15,18}, {16,20}

一般来说，要确定嵌套，您可以根据左端点(如您的示例)对间隔进行排序，然后在看到 {x,y}, {x',y'} 时运行并开始新的嵌套。与 y < x' .

对于嵌套，“基本间隔”由值的排序序列(无重复)形成。在这个例子中，嵌套给

(1,3,5,10,11) -> {1,3}, {3,5}, {5,10}, {10,11}

和

(15,16,18,20) -> {15,16}, {16,18}, {18,20}

所以整个算法可能是这样的:

• 根据左端点对区间进行排序
• 运行间隔直到 {x,y}, {x',y'}与 y < x'
• 从开始到 {x,y} , 制作排序的端点列表(无重复)，比如 a0,a1,...,ak
• 添加基本区间 {ai,a(i+1)}对于 i = 0...k-1
• 删除间隔 {x,y}并从第 2 步继续