arrays - 遍历两个数组，删除perl中的重叠

我有两组范围，分别由[start，stop]值表示。某些范围重叠，这意味着一个范围的起点在另一范围的[起点，终点]之间。我想创建一组新的范围，这些范围没有这样的重叠，并且也不包含范围内的任何新值。

范围如下所示:

@starts  @ends
      5    108
      5    187
     44    187
     44    229
     44    236
     64    236
    104    236
    580    644
    632    770

我期望的输出是这样的:

@starts  @ends
      5    236
    580    770

这是因为前七个范围与5 => 236的间隔重叠，而后两个范围与632 => 770的间隔重叠。

这是我尝试的代码:

$fix = 0;
foreach (@ends) {
    if ($starts[$fix + 1] < $ends[$fix]) {
        splice(@ends, $fix, $fix);
        splice(@starts, $fix + 1, $fix + 1);
    } else {
        $fix += 1;
    }
}

我可以自己打印出这些值，我只需要有关合并算法的帮助。

最佳答案

这将就地编辑数组，重叠时只是折叠边界。

# Since they're sorted by @starts, accept the 0th interval, start at 1
for (1..$#starts) {
    # extra check on array bounds, since we edit in-place
    last unless $_ < @starts;
    # don't need to collapse if no overlap with previous end
    next unless $starts[$_] <= $ends[$_-1];
    # delete this start and the previous end
    splice(@starts,$_,1);
    splice(@ends,$_-1,1);
    # rerun this loop for the same value of $_ since it was deleted
    redo;
}