在重叠间隔中查找基本间隔

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}省略了答案，因为它是 不存在的输入。
• 由于在{3,10}中定义的起始点“3”在 中，输入中的区间{1,5}已被分割为{1,3}，{3,5} 将间隔分成两个基本区间的输入。在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'
• Fr OM开始{x,y}，使端点（不重复）的排序列表，说a0,a1,...,ak
• 为i = 0...k-1
• 删除间隔加起来基本间隔{ai,a(i+1)}到{x,y}和步骤2

Answer 2

一个简单的算法是简单地通读整个数字列表，并为每一对中的每个项目创建一个元素。

每个元素将存储两个值：number，以及它是第一个还是第二个数字（来自输入）。然后

那些对将进行排序，首先通过其内部number，然后由它的位置（second将first之前去）

要打印出间隔的列表，你将与下一一起打印每个号码号，以下规则：

• 你不会打印重复的数字（因此，例如，你不会打印5,5）
• 如果你完全有second号码，然后first号码，您不会打印该基本间隔，因为该范围内没有值。

Answer 3

您可以对端点进行排序，然后按顺序进行迭代。为了知道你是否进出，你可以保留每个点的间隔数。 区间的左端有助于+1，而右有助于-1： （请注意，我用的TreeMap，这是排序）

static class Pair<T, K> { 
    public Pair(T first, K second){ 
     this.first = first; 
     this.second = second; 
    } 

    public String toString(){ 
     return "(" + first + ", " + second + ")"; 
    } 

    T first; 
    K second; 
}  

static List<Pair<Integer, Integer>> generateElementaryIntervals(List<Pair<Integer, Integer>> intervals) { 
    TreeMap<Integer, Integer> overlaps = new TreeMap<Integer, Integer>(); 
    for(Pair<Integer, Integer> interval : intervals){ 
     int value = overlaps.containsKey(interval.first) ? overlaps.get(interval.first)+1 : 1; 
     overlaps.put(interval.first, value); 

     value = overlaps.containsKey(interval.second) ? overlaps.get(interval.second)-1 : -1; 
     overlaps.put(interval.second, value); 
    } 

    List<Pair<Integer, Integer>> retValue = new ArrayList<Pair<Integer,Integer>>(); 

    int overlap = 0; 
    boolean in = false; 
    int last = 0; 
    for(int point : overlaps.keySet()){ 
     if(in) 
      retValue.add(new Pair(last, point)); 

     overlap += overlaps.get(point); 
     last = point; 
     in = overlap > 0; 
    } 

    return retValue; 
}  

public static void main(String[] args) { 

    List<Pair<Integer, Integer>> l = new ArrayList<Pair<Integer, Integer>>(); 
    l.add(new Pair<Integer, Integer>(1,5)); 
    l.add(new Pair<Integer, Integer>(3,10)); 
    l.add(new Pair<Integer, Integer>(5,11)); 
    l.add(new Pair<Integer, Integer>(15,18)); 
    l.add(new Pair<Integer, Integer>(16,20)); 

    for(Object o : generateElementaryIntervals(l)){ 
     System.out.println(o.toString()); 
    } 

}