Kow*_*hik 9 algorithm data-structures
在准备一些编程访谈时,我遇到了一个很好的问题.
给定一组可能重叠的区间,您需要编写一个函数来返回它们之间的所有基本区间.例如:如果给定间隔作为以下对列表:{{1,5},{3,10},{5,11},{15,18},{16,20}},那么您需要返回以下内容:
{{1,3},{3,5},{5,10},{10,11},{15,16},{16,18},{18,20}}
请注意以上答案中的以下内容:
Java中的方法签名:
List<Pair<Integer, Integer>> generateElementaryIntervals(List<Pair<Integer, Integer> intervals)
我想象的解决方案之一是将输入分成非交叉集,然后对每个非交叉集中的所有数字进行简单的O(NlogN)排序将得出答案.有更有效的方法吗？
您可以先将此问题分解为嵌套间隔,然后分别处理每个嵌套.通过嵌套,我的意思是至少共享一个点的间隔.对于您给出的示例:
{{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步并继续