將區間插入不相交的區間集合

給定排序的不相交集合(p,q）其中‘p’是開始時間，‘q’是結束時間。你會得到一個輸入間隔。將它插入正確的地方。並返回結果排序的不相交集合。將區間插入不相交的區間集合

Eg: (1,4);(5,7);(8,10);(13,18) 

Input interval – (3,7) 
Result : (1,7);(8,10);(13,18) 

Input Interval – (1,3) 
Result: (1,4);(5,7);(8,10);(13,18) 

Input interval – (11,12) 
Result: (1,4);(5,7);(8,10);(11,12);(13,18)

Inserting an interval in a sorted list of disjoint intervals，這裏沒有有效的答案

來源

2013-01-22 Peter

你是否假設你的初始間隔被排序？如果是這樣，怎麼樣？ – Dan

你的問題是什麼？ –

排序爲，它們是不相交的，在數字行之前出現的間隔是 – Peter

你的問題和例子暗示非重疊的時間間隔。在這種情況下，您只需執行binary search - 無論是通過開始時間進行比較還是結束時間對於非重疊間隔都無關緊要，並且可以在找到的位置插入新間隔（如果尚未存在）。

UPDATE

我錯過了在第一個例子中產生的合併。一個不好的情況是將一個較大的時間間隔插入一長串短時間間隔中，其中長時間間隔與很多短時間間隔重疊。爲了避免線性搜索所有必須合併的間隔，可以執行兩個二進制搜索 - 左起一個比較開始時間，右起一個比較結束時間。

現在，確定間隔是否存在，必須插入或必須與兩次搜索找到的位置之間的間隔合併在一起是微不足道的。雖然這不是很複雜，但它可能非常容易出現off-by-one errors，並且需要進行一些測試。

來源

2013-01-22 17:40:53

如第一個例子所示，您可能還必須合併間隔。無論如何，如果原始插播已排序，它仍然是一個簡單的任務;） – Dan

我想補充說，如果您的間隔與已經存在的間隔重疊，您可以在插入點合併間隔。 –

哦，錯過了那個，謝謝！將解決答案。 –

將區間插入不相交的區間集合

回答

相關問題