在重疊間隔中查找基本間隔

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()); 
    } 

}