完全にオーバーラップする間隔または範囲を削除する

Question

今日、私は以前、重複した間隔（または範囲、間隔）を削除することについて、明らかにひどく形成され、したがって既に削除されていました。問題は、完全に他の間隔内にある間隔を取り除く方法でした。わずかに良い可視化

1-2 
2-3 
1-3 
2-4 

または場合：

1-2 
    2-3 
1---3 
    2---4 

間隔1-2と2-3の両方が削除され、それらは間隔1-3に含まれているので、その出力は次のようになります。たとえば、私たちは以下の持っている

1-3 
2-4 

先験的アルゴリズムアルゴリズムは、おそらくすべての間隔O（n ）の比較をもたらす。誰かが処理前にソースデータを並べ替えることを提案しましたが、この問題には他の角度がありますか？

明白な例は、（データのソート）している：あなたはデータや提携タグでの素敵な落とし穴や他の例を思い付く場合

1-3 remove 
1--4 

1-3 remove this or next 
1-3 

1--4 
2-4 remove 

1---5 
2-4 remove 

1-3 print this, maybe next depending on the one after that 
2-4 

は、それらを追加してください。

Answer 1

誰かによって示唆されているように、このソリューションは、データを処理する前にソートされることを想定して：AWKで

$ sort -t- -k1n -k2n file # playin' it safe 
1-2 
1-3 
2-3 
2-4 

：

$ cat program.awk 
BEGIN { OFS=FS="-" } 
{ 
    if(p=="") {      # if p is empty, fill it 
     p=$0      # p is the previous record 
     next 
    } 
    split(p,b,"-")     # p is split to start and end to b[] 

    if(b[1] == $1 && b[2] <= $2) { # since sorting is expected: 
     p=$0      # if starts are equal p line is included or identical 
     next      # so remove it 
    } 
    else if($2 <= b[2])    # latter is included 
     next 

    print p       # no complete overlap, print p 
    p=$0       # and to the next 
} 
END { print p } 

を実行し、それは：

$ awk -f program.awk <(sort -t- -k1n -k2n file) 
1-3 
2-4 

または

1-2 
    2-3 

Answer 2

は限りアルゴリズムは多項式の複雑さを持っているとして、私は簡単な解決策が同様にOKだと思う：

#!/usr/bin/gawk -f 

BEGIN { 
    FS=OFS="-"; 
} 
{ 

    arr[NR][1] = $1; 
    arr[NR][2] = $2; 
} 
END { 

    for(i in arr) { 

     delete_nxt_elem(i); 

     if(arr[i][1]!="") 
      print arr[i][1],arr[i][2]; 
    } 
} 

function delete_nxt_elem(check_indx, j) { 

    for(j in arr) { 

     if(j==check_indx) 
      continue; 

     if(arr[j][1]<=arr[check_indx][1] && arr[j][2]>=arr[check_indx][2]) 
      delete arr[check_indx]; 
    } 
}