オーバーラップ間隔での基本的な間隔の検索

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}で定義されているので、 その間隔を2つの基本間隔に切断する入力。 Javaで

メソッドシグネチャ：私は想像溶液の

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

一つの非交差セットに入力を分離し、そして単純なO（NlogN）の各々における全ての数を超えるソートするました交差していない集合が答えを出す。より効率的な方法がありますか？

Answer 1

あなたが対処し、その後、最初のネストされた間隔にこの問題を破ることができます：右が寄与する-1間隔の 左端には、1を貢献しますそれぞれ別々にネストします。ネストされているとは、少なくとも1つの点を共有する区間を意味します。あなたが与えた例：

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

2つのネストがあります。一般的には

{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 {x,y}に始めオム、エンドポイントのソートされたリスト（繰り返しなし）を作る、a0,a1,...,ak
• は素の間隔を追加i = 0...k-1
• ため{ai,a(i+1)}は、ステップ2から

Answer 2

単純なアルゴリズムは、数字のリスト全体を読み、各ペアの各項目の要素を作成することです。

各要素には、numberという2つの値と、入力からの最初の番号か2番目の番号かが格納されます。

これらのペアは、最初にその内部numberによって、ソートされるだろう、とその位置によって

は間隔のリストを印刷するには（secondがfirst前に行くだろう）、あなたは次のと一緒に各番号を印刷します数は、次の規則で：

• あなたが排他的にsecond番号をお持ちの場合は繰り返し番号（そうたとえば、あなたは5,5を印刷しません）
• を印刷した後、ないだろうその範囲内に値がないため、その基本区間は印刷されません。

Answer 3

エンドポイントをソートして、順番に反復することができます。あなたが出入りしているかどうかを知るために、各ポイントをカバーする間隔の数を保持することができます。 を（私がソートされ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()); 
    } 

}