オーバーラップする数値領域のゲインとロスの計算

Question

2番目と3番目の列の数値は範囲を指定します。オーバーラップ領域を計算し、右側の数値で決定される範囲内のいくつの数を計算するか（最初の列の数値が同じ場合）+1（= 1が得られ、-1 = 1つは失われた）。 Iこれは1 100 200は1 0 300は0 100 +2、100 200 +1と200 300 +2しかし2 100 200作成と重なるので、私は実際

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

を持っていることを意味しない重なりを持たず、単に2 100 200 -1

を出力

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

ている場合、例えば サンプル入力

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

期待される結果

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

これはいいだろう実現する方法のための擬似コードのいくつかの並べ替え

しかし、私のために働くだろう言語はのためにbashのは、perlの、AWKやsedの

Answer 1

です最初の列のそれぞれ異なる値は、分割された範囲の開始点と終了点のリストを作成します。

ソートこれらの点

データの各ラインについて

、限界の間のすべての範囲にデルタ値を追加

（それらが隣接しており、同じ値で終わる場合は、複数の範囲を組み合わせることができる）

結果を出力

Answer 2

データをハッシュテーブルに格納します。一番上のキーはid（1 ^st列）です。第2レベルのキーは、「ブレーク」、すなわちゲインが変化する領域の境界線である。値はゲインがどれだけ変化するかです。

出力を印刷するときは、実行中のゲインを維持して、そこに格納された値を追加してください。結果がゼロでない場合はprintを返します。出力は期待どおりではないことに注意してください。しかし、ペンとペーパーで問題を解決しようとすると私は苦労します。

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

出力：

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