計算重疊日期範圍的問題

我試圖計算出一組日期範圍的正確算法時遇到問題。計算重疊日期範圍的問題

基本上我有一個無序的日期範圍列表（列表包含開始和結束時間的數組），我想合併這個列表，因此它不包含重疊時間。

基本上鞏固兩個日期範圍：

if start1 <= end2 and start2 <= end1 //Indicates overlap 
    if start2 < start1 //put the smallest time in start1 
     start1 = start2 
    endif 
    if end2 > end1 //put the highest time in end1 
     end1 = end2 
    endif 
endif

此連接兩個日期倍。

在迭代所有值時，我碰到了一個絆腳石，因此結束列表只包含不重疊的值。

我的功能和遞歸編程有點生疏，任何幫助都會受到歡迎。

來源

2011-09-19 emt14

http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844包含一個解決方案和解釋（這取決於你正在優化什麼，你沒有指定那..）。應該很容易實現在FP –

任何機會，你可以把我正確的方向，你正在引用哪種算法，數據結構或方法？ – emt14

我認爲它在貪婪算法部分的開頭（儘管我不確定）。你必須先排序列表。 –

不要看間隔，只看他們的結局。

你有一堆起始時刻和一堆結束時刻。想象一下，開始的時刻是紅色的，結束的時刻是藍色的。或者想象一下，開始的時刻正在開啓大括號，結束的時刻正在關閉大括號。

將它們全部放在一個列表中。從最早到最新對列表進行排序，忽略顏色。

現在把你的計數器設置爲零，然後走下列表。當你看到一個紅色的時刻，增加計數器。當你看到一個藍色的時刻，減少櫃檯。當計數器值從0變爲1時，輸出「開始」和當前時間。當計數器值從1變爲0時，輸出「結束」和當前時間。如果計數器值低於0，輸出「休斯頓，我們有問題」。你應該以0的計數器和一堆不錯的非重疊間隔結束。

這是很好的老支架計數算法。

插圖。

A bunch of overlapping intervals: 

(-------------------) 
         (----------------------)   
                  (---) 
     (---------------------)      
                (-----------------) 

A bunch of interval ends: 

(-----(-------------)-(-----)----------------)  (----(---)--------)

來源

2011-09-19 10:15:37

工程一個治療，實現起來非常簡單。謝謝，我不認爲我正朝着正確的方向前進！ – emt14

這個算法對於我在預約系統中統計資源分配的另一個問題非常有效。目標是從固定數量的一些資源開始，並確定是否有人可以檢出或保留其他人以前所做的相同總數的子集。 – agent154

N.M.的答案是所有你需要的，但如果你想使用你已經取得的代碼，然後簡單地通過範圍的開始時間和排序在列表合併重疊走。

來源

2011-09-19 10:32:16 quasiverse

計算重疊日期範圍的問題

回答

相關問題