如果可能，将任意间隔集合转换为连续间隔集合

Question

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

假设我有一组正常数字的间隔。 例如N1 = {（0,1]，（1,2]，（3,4）}; 我想将此设置最小化为： N2 = {（0,2]，（3,4]};

所以基本上我需要的是多小的间隔组合成连续的时间间隔，它是可能的。

是否有所作所为这个任何聪明/高效的算法呢？因为我想避免低效的for-each-ING 。

*如果这个问题有一定的宽熟知的名字，请在评论名字。

Answer 1

这是一个sweep-line algorithm。

• 将区间拆分为开始点和结束点。

• 对点进行排序。

• 令数= 0

• 迭代通过点：

  • 每当你遇到一个终点：

    • 递减计数。

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

  • 每当遇到起点时，

    • 如果count = 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]}。