我使用一列数据来表示分散的数据块：

[(offset0, size0), (offset1, size1), (offset2, size2), ...]

这列数据根据 offset 从小到大排序的，并且块与块之间不重叠。

当我插入一个新的块 (offset3, size3) 时，希望让新块相邻的重叠块融合起来，如果不重叠的话就插入适当的位置。有什么算法方便地做到这件事吗？

需要注意的是，这个新的块，可能和两个旧的块重叠，此时需要把三个块粘起来，变成一个块。因为我们的这个列表，总是需要满意块与块之间不重叠这个条件。
--
FROM 124.72.118.*

想了一下。。好像不难。

先根据 offset3 插入到指定的位置。然后看看前后两个块的情况，一前一后连接起来就行了。

【 在 hgoldfish (老鱼) 的大作中提到: 】
: 我使用一列数据来表示分散的数据块：
: [(offset0, size0), (offset1, size1), (offset2, size2), ...]
: 这列数据根据 offset 从小到大排序的，并且块与块之间不重叠。
: ...................
--
FROM 124.72.118.*

你这个叫Merging Overlapping Intervals，网上有很多类似算法比如
https://stackoverflow.com/questions/43600878/merging-overlapping-intervals

【 在 hgoldfish (老鱼) 的大作中提到: 】
: 我使用一列数据来表示分散的数据块：
: [(offset0, size0), (offset1, size1), (offset2, size2), ...]
: 这列数据根据 offset 从小到大排序的，并且块与块之间不重叠。
: ...................
--
FROM 27.91.71.*

这个不难，数据结构合适的话（比如C++的map）单次插入是O(lg n), n=现有块的个数
--
FROM 183.179.53.*

赞。。

【 在 z16166 (Netguy) 的大作中提到: 】
: 不难，leetcode上也有这题
: https://leetcode.com/problems/merge-intervals/
: https://www.geeksforgeeks.org/merging-intervals/
: ...................
--
FROM 124.72.118.*