c++ - 将小的重叠 block 合并为较大的连续 block 的有效算法？

Question

我面临一个相当有趣的问题。我有(相当大)数量的 block 。 block 只是从偏移量开始并具有长度和颜色的东西。偏移量和长度是有限的——这些 block 所在的空间是<0-N>，其中N的范围从几十万到几百万。无效 block 是偏移量大于 N 或偏移量和长度之和大于 N 的任何 block 。 block 可能有大约 16 种不同的颜色(只是其中一种)。

可能有几千 block ，总有这样的情况:

block_X: off: 100, len: 50, color: blue
block_Y: off: 148, len: 50, color: blue
block_Z: off: 200, len: 30, color: red

如您所见，X 和 Y block 可以连接成一个更大的 block ，结果是:

block_XY:关闭:100，len 98，颜色:蓝色
block_Z: off 200, len 30, color: red

我想创建一个算法来遍历所有 block 并将那些重叠且具有相同颜色的 block 连接起来。实际上，如果 block 之间的间隙相当小(我可以选择一个常数，比如大约 16 左右，但可以是任何数字......)那么我无论如何都想连接这些 block 。请注意，在上面的示例中，只有两个 block 连接在一起。实际上，大部分时间可以连接的 block 序列要长得多。

还有一个有趣的转折，考虑一下:

block_A: off: 100, len: 200, color: blue
block_B: off: 200, len: 200, color: blue
block_C: off: 300, len: 150, color: red
block_D: off: 400, len: 200, color: blue
block_E: off: 500, len: 200, color: blue

如您所见，我们有一系列漂亮的蓝色 block ，可以将它们合并成一个大的蓝色 block 。但是，它的中间也有一个红色的小块。这应该不会骗过算法，正确的结果是:

block_ABDE: off: 100, len: 600, color: blue
block_C: off: 300, len: 150, color: red

数据存储在 std::multimap 中，其中键是偏移量，值是包含 block 的长度和颜色的结构，类似于:multimap<uint32_t,pair<uint32_t, uint8_t> > .请注意，可能存在以相同偏移量开始的 block 。但是可以保证，如果发生这种情况，以相同偏移量开始的 block 具有不同的颜色和不同的长度。

谁能想出一个好主意如何有效地解决这个问题？ 该算法的目标是减少我们拥有的 block 数，但并不要求将其减少到尽可能小的数量。

Answer 1

我建议如下:

1. 为每种颜色创建一个单独的列表
2. 对于每种特定颜色，计算所有 block 的开始(偏移)和结束(偏移+长度)
3. 按开始值对每个特定于颜色的列表进行排序
4. 现在，遍历每个列表，合并项目:如果下一个项目的开头小于或等于前一个项目的结尾(加上允许的间隙)，则删除下一个项目并扩展前一个项目。