時間の重複のリストが

Question

タイトルが素晴らしいではありません予定の集合の範囲を取得し、私は提案を開いています。私は予定のセット、開始時刻と終了時刻と各を持って

：

は、ここに私の基本的な問題です。

このセットを指定すると、nの重複する予定があるすべての期間で、範囲の新しいセット[ start_time, end_time ]が表示されます。

そうは、例えば、セット（タイムスタンプが読みやすくするために少数のように簡略化）

[ [ 1, 3 ], [ 2, 4 ], [ 2, 4 ], [ 5, 7 ], [ 6, 8 ], [ 7, 8 ] ]

...と私はそれらの中で発生、少なくとも3種類の予定を持っているすべての範囲をしたいと仮定すると与えられました結果は

...これは少しあまり抽象的にするために

[ [ 2, 3 ], [ 6, 7 ] ]

する必要があります

私は、常に3人のインストーラをスタッフが常駐させて24時間のウィンドウティントサービスを実行するとします。私のウェブサイトでは、利用可能なインストール時間をすべて表示したいと考えています。だから私はすでに3つの予定を予定している時間範囲を隠す必要がある。

は必ずしもコードを書く人を求めていない - 誰かがに私を指すことができることを問題のこのクラスのためのよく知られたアルゴリズムがありますならば、私はそれを感謝します。

ありがとうございました。私はノードでこれを実装することがありますので

[EDIT]はjavascriptのタグを追加しましたが、答えはJSである必要はありません。

[EDIT 2]私はかなり一般的な解決策を探して、それでは、予定が（時間または30分塊に正規化されていない）とあなたと仮定すると、任意の期間

Answer 1

ペアの配列/リストを作成します：タイムキーによる{time, flag = +1 for start of interval, -1 for the end of interval}

ソートリストを。 （開始前終了[1,2]と[2,3]などの間隔が交差してはならない場合）、開始/終了フラグのためのネクタイアカウントの場合は

Counter = 0

トラバースリストを作成し、各ペアのためCounterにフラグを追加します。ときn-1nからCounter変更 - 出力範囲が始まり、nn-1からCounter変更する場合 - 出力範囲が

Answer 2

にすることができ、いつでも始めることができるとしましょうよ30分間隔で物事を置くことができます。そして、最初の間隔で＃appts = 0で開始し、すべての間隔ポイントで、現在開始されているすべてのapptに対してインクリメントし、今終了したapptごとにインクリメントします。 #apptsは現在のインターバルでアクティブなアペットの数を常に追跡します。

あなたが効率的に、あなたができる「バケットソート」あなたの開始終了は、各区間のためのバケットに回を終了本当にクレイジーになりたい場合は、全体のプロセスは線形になります。しかし、あなたが非常に多くのアポイントメントを持っていない限り、それはあなたが進むにつれてそれらを見上げるように働くでしょう。

Answer 3

は、私はそれが3

ところで、この場合には、その後、入力範囲からヒストグラムを作成し、高さがより大きいか、あなたのターゲットの重なりに等しい範囲を特定するヒストグラムを反復処理するために、Iドンをうまくいくと思いますあなたの入力を考慮して[6,7]が有効範囲であると思う - 私はそれが[7,7]であるべきだと思う。少なくともそれは私のコードが生成するものです:)ここ

は説明するためにいくつかのJavaコードです：

public static void main(String[] args) 
{ 
    int[][] ranges = {{1,3},{2,4},{2,4},{5,7},{6,8},{7,8}}; 

    int min = Integer.MAX_VALUE; 
    int max = Integer.MIN_VALUE; 
    for(int[] range : ranges) 
    { 
     min = Math.min(min, range[0]); 
     max = Math.max(max, range[1]); 
    }  

    int[] hist = new int[1+max-min]; 
    for(int[] range : ranges) 
     for(int i=range[0]; i<=range[1]; i++) hist[i-min]++; 

    int overlap = 3; 
    for(int i=0; i<hist.length; i++) 
    { 
     int j = i; 
     while(i<hist.length && hist[i] >= overlap) {i++;} 
     if(i>j) 
      System.out.println((j+min) + " : " + (i+min-1)); 
    } 
} 

出力：

2 : 3 
7 : 7 

EDIT

私は以来、ヒストグラムアプローチに不満でしたそれは整数範囲に依存し、長い範囲に対しては非効率的である。あなたが代わりにレンジエンドポイントをソートし、レンジの開始または終了を追跡してから、アクティブ範囲のカウンタを保持しているエンドポイントを歩いていくことができました。遭遇する）。カウンターが最初に上がったり、しきい値を下回ったりすると、ケース3では範囲を出力します。

私はMBoがこれと同じアプローチを提案しています。

ここではいくつかのより多くのコードを説明するためにです：

static class RangeEnd 
{ 
    int time; 
    int delta; 
    public RangeEnd(int pos, int delta) 
    { 
     this.time = pos; 
     this.delta = delta; 
    } 
} 

public static void main(String[] args) 
{ 
    int[][] ranges = {{ 1,3},{2,4},{2,4},{5,7},{6,8},{7,8}}; 

    RangeEnd[] ends = new RangeEnd[2*ranges.length]; 

    int i=0; 
    for(int[] range : ranges) 
    { 
     ends[i++] = new RangeEnd(range[0], 1); 
     ends[i++] = new RangeEnd(range[1], -1); 
    } 

    Arrays.sort(ends, new Comparator<RangeEnd>() 
    { 

     @Override 
     public int compare(RangeEnd e1, RangeEnd e2) 
     { 
      if(e1.time < e2.time) return -1; 
      else if(e1.time > e2.time) return 1; 
      else if (e1.delta > e2.delta) return -1; 
      else return 1; 
     } 
    }); 

    int overlap = 3; 

    int count = 0; 
    boolean active = false; 
    int start = 0; 
    for(RangeEnd end : ends) 
    { 
     count += end.delta; 
     if(count >= overlap) 
     { 
      if(!active) 
      { 
       start = end.time; 
       active = true; 
      } 
     } 
     else if(active) 
     { 
      System.out.println(start + " : " + end.time); 
      active = false; 
     } 
    } 
} 

Answer 4

は、あなたのタイムスタンプおよび範囲は、正確にどのようなものを求めますか？彼らは毎日/時間/ 30分/分ですか？

可能な解決策は次のとおりです。 あなたのタイムスタンプは時間特有のものです。 文字列のキーとint値を保持する辞書を宣言します。キーは時間に対するタイムスタンプを表す。 "08-30-17 23"。値は、その時間に予定されている予定の数です。

今すぐ範囲をループします。それぞれの範囲について、別のループを使用して開始時間と終了時間の間の時間を調べます。それらの時間のそれぞれについて、そのタイムスタンプのためにディクショナリ内のカウントを1ずつ増加させる（時間単位で）。

最後に、データの1時間ごとに予定されている数の会議を開催する必要があります。あなたが午後5時から午後6時まで、また午後6時と午後7時の間に3つのアポイントメントをお持ちの場合は、それを5〜7pmの範囲に変換するためにもっと論理が必要です。