Расчет прибылей и убытков областей перекрывающихся номеров

Question

Цифры во втором и третьем столбцах указывают диапазон. Я хочу, чтобы (если число в первом столбце одинаковое), чтобы рассчитать перекрывающиеся области и вычислить, сколько в диапазоне получено или потеряно, как определено числом справа (+1 = один полученный, -1 = один потерян). Например, если у меня есть

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

Это означает, что я на самом деле есть

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

потому 1 100 200 перекрывается с 1 0 300 создания 0 100 +2, 100 200 +1 и 200 300 +2 но 2 100 200 не имеет перекрытий и просто печатает 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 

Своего рода псевдокод для того, как сделать это было бы неплохо

Но языки, которые будут работать для меня являются Баш, Perl, AWK или СЭД

Answer 1

Для каждое отдельное значение первого столбца, создайте список всех начальных и конечных точек диапазонов, в которые он разбит.

Сортировка те точки

Для каждой строки данных, добавить значение дельта для всех диапазонов в пределах от

(Вы можете объединить несколько диапазонов, если они являются смежными и в конечном итоге с тем же значением)

Распечатать результат

Answer 2

Храните данные в хеш-таблице. Самый верхний ключ - это идентификатор (столбец 1 ^st). Клавиши второго уровня - это «разрывы», т. Е. Границы областей, в которых изменяется коэффициент усиления. Значения зависят от того, насколько изменяется коэффициент усиления.

При печати вывода просто сохраняйте коэффициент усиления и добавьте к нему сохраненное значение; напечатайте, если результат не равен нулю. Обратите внимание, что результат отличается от вашего ожидаемого, но я получил свое, когда пытался решить проблему ручкой и бумагой.

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