重複する日付範囲を計算する際の問題

Question

日付範囲のセットを計算するための正しいアルゴリズムを試してみるのに問題があります。

基本的には、順序付けられていない日付範囲のリスト（開始時刻と終了時刻の配列を含むリスト）があり、重複していない時間帯を含まないようにこのリストを統合したいと思います。

基本的に2つの日付の範囲統合する：

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 

をこれには2つの日付回に参加します。

すべての値を反復するときにぶつかり合ってしまい、エンドリストには重複しない値しか含まれていません。

私の機能的で再帰的なプログラミングは少し錆びていて、どんな助けでも歓迎されます。

Answer 1

間隔を見ないで、端だけを見てください。

あなたには始まりの瞬間と終わりの瞬間の束があります。開始の瞬間が赤で、終了の瞬間が青であると想像してください。または、始点の瞬間が中括弧を開き、終わりの瞬間が中括弧で囲まれていると想像してください。

すべてをまとめてリストに入れます。色を無視して、リストを最も早いものから最新のものにソートします。

ここで、カウンタをゼロに設定してリストを歩きます。赤い瞬間が見えたら、カウンターを増分してください。青い瞬間が見えたら、カウンターを減らしてください。カウンタ値が0から1になると、 "start"と現在時刻が出力されます。カウンタ値が1から0になると、 "end"と現在時刻が出力されます。カウンタ値が0より下に下がった場合、 "ヒューストン、我々は問題がある"と出力する。あなたは0であなたのカウンターで終わるべきで、すばらしい重複しない間隔の束。

これは古い古いブレースカウンティングアルゴリズムです。

イラスト。

A bunch of overlapping intervals: 

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

A bunch of interval ends: 

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

Answer 2

N.M.の答えはあなたが必要なすべてのですが、あなたは、単に開始時間によって範囲をソートし、重複をマージリストを歩くあなたがすでに作られたコードを使用する場合。