如果可能，將任意間隔集合轉換爲連續間隔集合

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]}。