交替布尔范围的二维正交加法投影

Question

我有几个可变长度的数组，其中填充了表示好数据块和坏数据块的元组。

input = [
    [(True, 0, 400), (False, 400, 500), (True, 500, 1000)],
    [(True, 0, 200), (False, 200, 400), (True, 400, 1000)],
    [(False, 0, 100), (True, 100, 1000])]]

我想要做的是创建一个新的元组列表，这些元组表示在我的所有数组中都适用的数据块。以上结果如下。

output = [(False, 0, 100), (True, 100, 200), (False, 200, 500), 
         (True, 500, 1000)]

每个原始数组中的元组保证是交替的True和False。每个数组也将具有相同的开始和结束（在上述情况下为 0 和 1000）。

test = fn(input)
assert test == output

我的目标是在 O(n) 时间内完成这项工作，但我一直无法弄清楚。

Answer 1

所以你必须采用假范围可能重叠的并集。 True 范围可用于查找 0 - 1000。最后添加真实范围以填补空白。

....FFF...FFF...FFFFF.... old partial result, initially empty
......FFFFFFFFFFF.....F.. next input ranges
------------------------- union
....FFFFFFFFFFFFFFFFF.F.. new partial result

因此对输入建模：

record Range(boolean onoff, int x1, int x2) { }

Range[][] input = {
    {new Range(true, 0, 400), new Range(false, 400, 500), new Range(true, 500, 1000)},
    {new Range(true, 0, 200), new Range(false, 200, 400), new Range(true, 400, 1000)},
    {new Range(false, 0, 100), new Range(true, 100, 1000)}
}:

List<Range> accumulatedFalse new ArrayList<>();
for (Range[] ranges: input) {
    int x0 = 0;
    for (Range range: ranges) {
        if (!range.onoff) {
            // Accumulate this range:
            ... check for any overlapping and update accumulatedFalse 
        }
    }
}
... Fill True ranges in the gaps ...

当然，我不会破坏编写代码的乐趣。

Answer 2

基本上，您想合并数组。您可以成对进行：首先，将第一个数组与第二个数组合并，然后将结果与第三个数组合并，依此类推。

两个数组如何合并？运行一个有两个索引的循环，当在第一个数组上时，第二个在第二个数组上。在每次循环迭代中，您递增其中一个索引，该索引代表具有较低数据位置的元组。然后逐个元组合并数组。

例如，让我们考虑您的前两个数组。

[(True, 0, 400), (False, 400, 500), (True, 500, 1000)],
[(True, 0, 200), (False, 200, 400), (True, 400, 1000)],

我们从 i 指向 (True, 0, 400) 和 j 指向 (True, 0, 200) 开始。 None 为假，所以我们的输出以 (True, 0, 200) 开头（这两个元组的公共部分）。然后我们递增 j（因为它的元组以 200 结尾）。

在下一次迭代中，i 和 j 分别指向元组 (True, 0, 400) 和 (False, 200, 400)。我们合并它们，得到 (False, 200, 400)，我们将其添加到我们的输出中。现在两个元组都以相同的数据位置结尾，所以我们都递增。

接下来，我们得到元组 (False, 400, 500) 和 (True, 400, 1000)。我们将它们合并以获得 (False, 400, 500)。因为我们输出中的最后一个元组是 False，而不是再添加一个 False 元组，我们只是将输出中的最后一个元组扩展为 500。我们递增 i.

在最后一次迭代中，(True, 500, 1000) 和 (True, 400, 1000) 我们合并得到 (True, 500, 1000).

因此，我们的输出是[(True, 0, 200), (False, 200, 500), (True, 500, 1000)]。

交替布尔范围的二维正交加法投影

Two-dimensional orthogonal additive projection of alternating boolean ranges

algorithm

data-structures