algorithm - 在可能的情况下，将任意间隔集转换为连续间隔集

Question

我有一个实际情况，我需要最小化数据量。

假设我得到了一组正常数字的区间。例如 N1 = {(0,1],(1,2],(3,4]}; 我想将此集最小化为： N2 = {(0,2],(3,4]};

所以基本上我需要的是在可能的情况下将多个小间隔组合成连续的间隔。

是否有任何聪明/有效的算法可以做到这一点？因为我想避免 for-each-ing 效率低下。

*如果这个问题有一些广为人知的名字，请在评论中命名。

Answer 1

这是一种扫线算法。

• 将间隔分成起点和终点。

• 对点进行排序。

• 设计数 = 0。

• 遍历点：

  • 每当你遇到一个终点：

    • 减少计数。

    • 如果计数 = 0，记录这一点。

  • 每当你遇到一个起点。

    • 如果计数 = 0，记录这一点。

    • 增加计数。

作为技术说明，在排序时，如果起点和终点具有相同的值，请将起点放在第一位，否则您可能会将其记录为间隙，而不是连续间隔。

例子：

(0,1],(1,2],(3,4]

Split    0 start, 1 start, 1 end, 2 end, 3 start, 4 end
Count       1        2        1     0        1      0
Record      (0      N/A      N/A    2]      (3      4]

获取记录的值给了我们{(0,2], (3,4]}。