Berechnen von Verstärkungen und Verlusten von überlappenden Nummernbereichen

Question

Die Zahlen in der zweiten und dritten Spalte geben einen Bereich an. Was ich will, ist (wenn die Zahl in der ersten Spalte gleich ist), überlappende Regionen zu berechnen und zu berechnen, wie viele in einem Bereich durch die Zahl rechts gewonnen oder verloren werden (+1 = eins gewonnen, -1 = man hat verloren). Zum Beispiel, wenn ich

1 0 300 +2 
1 100 200 -1 
2 100 200 -1 

Das bedeutet, habe ich tatsächlich

1 0 100 +2 
1 100 200 +1 
1 200 300 +2 
2 100 200 -1 

weil 1 100 200 Überschneidungen mit 1 0 300 Schaffung 0 100 +2, 100 200 +1 und 200 300 +2 aber 2 100 200 keine Überschneidungen hat und druckt einfach 2 100 200 -1

aus Beispieleingabe

1 0 5000 +1 
1 100 400 -1 
1 300 500 +2 
1 1000 1200 +3 
1 1000 1100 -2 
1 0 50 -1 

erwartete Ergebnis

1 50 100 +1 
1 300 400 +1 
1 400 500 +3 
1 1000 1100 -1 
1 1100 1200 +2 
1 1200 5000 +1 

Irgendeine Art von Pseudo-Code für wie dies erreichen würde

Aber Sprachen nett sein, die für mich arbeiten würde sind Bash, Perl, awk oder sed

Answer 1

Für Jeder eindeutige Wert der ersten Spalte erstellt eine Liste aller Start- und Endpunkte der Bereiche, in die er unterteilt ist.

sortiert diese Punkte

Für jede Zeile von Daten, den Delta-Wert für alle Bereiche hinzufügen, zwischen den Grenzen

(Sie mehrere Bereiche kombinieren können, wenn sie nebeneinander und am Ende mit dem gleichen Wert sind)

Drucken Sie das Ergebnis

Answer 2

Speichern Sie die Daten in einer Hash-Tabelle. Der oberste Schlüssel ist die ID (die Spalte 1 ^st). Tasten der zweiten Ebene sind die "Unterbrechungen", d. H. Die Grenzen der Bereiche, in denen sich die Verstärkung ändert. Die Werte geben an, um wie viel sich die Verstärkung ändert.

Wenn Sie die Ausgabe drucken, behalten Sie einfach eine laufende Verstärkung bei und fügen Sie den gespeicherten Wert hinzu; Drucken, wenn das Ergebnis nicht Null ist. Beachten Sie, dass sich die Ausgabe von der erwarteten unterscheidet, aber ich habe meine, wenn ich versuche, das Problem mit Stift und Papier zu lösen.

#!/usr/bin/perl 
use warnings; 
use strict; 
use feature qw{ say }; 

my %table; 

while (<>) { 
    my ($id, $from, $to, $gain) = split; 
    $table{$id}{$from} += $gain; 
    $table{$id}{$to} -= $gain; 
} 

for my $id (sort { $a <=> $b } keys %table) { 
    my $previous; 
    my $gain = 0; 
    for my $break (sort { $a <=> $b } keys %{ $table{$id} }) { 
     if (defined $previous) { 
      $gain += $table{$id}{$previous}; 
      say join "\t", $id, $previous, $break, $gain 
       if $gain; 
     } 
     $previous = $break; 
    } 
} 

Ausgang:

1  50  100  1 
1  300  400  2 
1  400  500  3 
1  500  1000 1 
1  1000 1100 2 
1  1100 1200 4 
1  1200 5000 1