计算重叠数区域的得失

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

关于如何实现这一点的某种伪代码会很好

但适合我的语言是 bash、perl、awk 或 sed

Answer 1

对于第一列的每个不同值，创建一个列表，列出其划分的范围的所有起点和终点。

对这些点进行排序

对于每一行数据，将增量值添加到限制之间的所有范围

（您可以组合多个范围，如果它们是相邻的并且最终具有相同的值）

打印结果

Answer 2

将数据存储在散列中 table。最上面的键是 id（第 1^st 列）。第二级键是 "breaks"，即增益变化区域的边界。这些值是增益变化的多少。

打印输出的时候，只保留一个运行增益，把存储的值加进去即可；如果结果不为零则打印。请注意，输出与您预期的不同，但我也是在尝试用笔和纸解决问题时得到的。

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

计算重叠数区域的得失

Calculating gains and losses of overlapping number regions

sorting

bash

perl

add