リストに日付が重複したままになる

Question

セッションの有効期限の時間とセッションのタイムアウト値のリストがあります。 セッションの開始時間から有効期限のタイムアウトを差し引くことができます。

私は2つの日付が重なっているかどうかを確認する方法を知っている：

public boolean isOverlapped(LocalDateTime start1, LocalDateTime end1, 
          LocalDateTime start2, LocalDateTime end2) { 
    return (start1.isBefore(end2) || start1.equals(end2)) 
      && (start2.isBefore(end1) || start2.equals(end2)); 
} 

が、日付のリストのためにこれを行うにはどのようには考えています。

結果私は、重複した（並行して）セッションの中で最も長いチェーンを持つリストを持っていたいと思います。 ありがとうございました！

Answer 1

まず第一に、（お持ちでない場合）、これらのセッションを表す新しいクラスを作る：

class Session { 
    private LocalDateTime start; 
    private LocalDateTime end; 

    public boolean isOverlapped(Session other) { 
     return (start.isBefore(other.end) || start.equals(other.end)) 
      && (end.isAfter(other.start) || end.equals(other.start)); 
    } 
    ...  
} 

ご入力リストはSession秒のリストである必要があります。

次に、質問したことを実行するアルゴリズムを示します。それはリスト内に入れて、それがのいずれかの他の要素と重複するならば（各要素を除く）、各要素をチェックします。その場合は、それが結果リストにそれを置く：ここ

public static List<Session> filter(List<Session> in) { 
    List<Session> result = new ArrayList<>(); 

    for(Session current : in) { 
     for(Session other : in) { 
      if(current != other && current.isOverlapped(other)) { 
       result.add(current); 
       break; 
      } 
     } 
    } 

    return result; 
} 

はまた、例えばプログラムです：Ideone

結果は、他のセッションと同時だったセッションを含むリストになります。

Answer 2

これはかなり古典的な問題です。時間の点で、または間隔の数で最も長いセッションを希望するかどうかは指定していませんが、どちらも同じ方法で動作します。

最初にすべてのセッションを開始時刻で並べ替えます。次に、ロジックは次のようになります。

current_chain = [] 
best_chain = [] 
for session in sessions_sorted_by_start: 
    if session doesn't overlap with any session in curent_chain: [1] 
     update best_chain if current_chain is better    [2] 
     current_chain = [] 
    current_chain.insert(session)         [3] 
update best_chain if current_chain is better      [2] 

ここでのアイデアは、現在のチェーンを維持することです。新しいセッションがチェーン内の他のセッションと重複している場合は、チェーンに追加するだけです。現在のチェーン内のセッションと重複しない場合は、現在のチェーン内の最も遠いセッションの最後から右に開始するので、他の残りのセッションは現在のチェーンのものと重複しません（開始日でソート）。つまり、現在のチェーンはこれまでと同じ長さであるため、これまでのベストセラーチェーン（[2]）よりも優れているかどうかを確認してリセットすることができます。

ここで、時間的に線形にするには、一定時間内に[1]でセッションとチェーンのオーバーラップチェックを行うのがいいでしょう。これは、チェーンのために常に最も遠いセッションを維持している場合には簡単に実行されます。これを行うには、[3]で新しいセッションを挿入するときに、その最後が現在の最も遠いセッションの終わりを超えている場合は、最も遠いセッションを更新し、そうでない場合は更新しないでください。この方法では[1]で最も近いセッションとのオーバーラップをチェックするだけで、すべてのチェックを行う代わりに、その特定のチェックを一定時間にし、アルゴリズム全体をリニアにする必要があります（初期ソートを考慮していない場合もちろんO(n log n)）。