Entfernen von sich völlig überlappenden Intervallen oder Bereichen

Question

Früher habe ich heute eine - scheinbar schlecht geformte und daher bereits gelöschte - Frage zum Entfernen überlappender Intervalle (oder Bereiche, Intervalle ab diesem Zeitpunkt) gesehen. Die Frage war, wie man Intervalle entfernt, die vollständig in anderen Intervallen liegen. Zum Beispiel haben wir folgendes:

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

oder wenn etwas besser sichtbar gemacht:

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

Intervalle 1-2 und 2-3 sind beide entfernt, da sie in dem Intervall enthalten sind 1-3 so wäre die Ausgabe:

A priori Algorithmus wäre wahrscheinlich jedes Intervall zu überprüfen gegen jeden anderen ergeben sich O (n) Vergleiche. Jemand hat vorgeschlagen, die Quelldaten vor der Verarbeitung zu sortieren, gibt es andere Aspekte für dieses Problem?

Offensichtliche Fälle sind (Daten sortiert):

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 

Bitte, wenn Sie mit netten Fallen oder anderen Fällen in den Daten oder verbundenen Tags sie hinzufügen kommen.

Answer 1

Diese Lösung erwartet, dass die Daten vor der Verarbeitung sortiert werden, wie jemand vorgeschlagen:

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

In awk:

$ 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 } 

Run it:

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

oder

1-2 
    2-3 

Answer 2

Solange der Algorithmus Polynom Komplexität hat, denke ich, die einfachste Lösung auch in Ordnung ist:

#!/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]; 
    } 
}