使用分段樹查找重疊區間的總長度？

例如[1; 4] [7; 13] [9; 14]的輸入應該返回3 + 6 + 1 = 10。有什麼方法可以動態地插入或刪除間隔時，使用分段樹來查找這些間隔的總長度？使用分段樹查找重疊區間的總長度？

P.S .:我想這樣做，而不使用分段樹，但時間複雜性不滿足我。

預先感謝您

來源

2013-01-25 CoderInNetwork

你有多少間隔和最大的最小位置和iterval的長度。有多少請求獲得總數，多少插入？ –

是按照你的例子排序的區間？ –

@AndyT是我可以先排序他們 – CoderInNetwork

讓我們假設該間隔被存儲在陣列[M，N]英寸另一個假設是數組被排序。

所有你需要做的是找到更小的差異：

int totalIntervales = 0; 
for(int index = 0; index < array.length ; index++) 
{ 
    int currentIntrval = array[index, 1] - array[index, 0]; 
    int differnceFromPrevious = array[index, 1] - array[index- 1, 1] 
    totalIntervale += currentIntrval > differnceFromPrevious ? differnceFromPrevious : currentIntrval; 
} 
return totalIntervale;

只是小心處理0位置。

來源

2014-03-01 17:05:56 Kobi

我想你的算法有一個錯誤，當第二個時間間隔完全包含在第一個時。考慮集合[1,4] [2,3]。你的算法會說間隔是2.解決的辦法是檢查differenceFromPrevious是否定的。否則，它似乎工作。（編輯是因爲我忘記點擊「輸入」會提交評論） – James

實際上，經過進一步的思考，我認爲你的算法不能很好地工作。以[1，5] [1，2] [2，4]爲例。你的算法會報告4 - 3 + 2 = 3。 – James

Kobi/Maureinik答案非常接近，但我必須爲maxEnd添加一個變量並檢查differenceFromPrevious是否定的。該算法仍然假定範圍的起始元件上的排序

int totalInterval = array[0, 1] - array[0, 0]; 
int maxEnd = array[0, 1]; 
for(int index = 1; index < array.length ; index++) { 
    int currentIntrval = array[index, 1] - array[index, 0]; 
    int differnceFromPrevious = array[index, 1] - maxEnd; 
    if(differenceFromPrevious >= 0) { 
    totalInterval += (currentIntrval > differnceFromPrevious) ? differnceFromPrevious : currentIntrval; 
    } 
    maxEnd = (maxEnd >= array[index, 1]) ? maxEnd : array[index, 1]; 
} 
return totalInterval;

編輯（即陣列[I，0]）：原始totalInterval邏輯的固定意外拷貝沒有工作。如果differenceFromPrevoius < 0，則應該單獨保留totalInterval。

來源

2014-05-05 20:56:46 James

使用分段樹查找重疊區間的總長度？

回答

相關問題