4

私はアルゴリズムをレビューしてきました、これはアナニ・レヴィチンのアルゴブックからの質問です。

実数直線上にn個の開区間（a1、b1）、...、（an、bn）のリストがあります。（開区間（a、b）は、その端点aとbの間のすべての点で構成されます。つまり、（a、b）=（xi a <x <b}）。共通のあるこれらの区間の最大数を見つけます。ポイント。たとえば、区間（1、4）、（0、3）、（-1.5、2）、（3.6、5）の場合、この最大数は3です。この問題のアルゴリズムを2次よりも優れたもので設計します。時間効率。

誰かが私がそれのためのアルゴリズムを形成するのを手伝ったり、インターネット上のリソースを提案したりできますか？

ありがとう、Hareendra

4

3 に答える 3

5

これにアプローチする1つの方法は、次のとおりです。実数直線上にすべての間隔を並べるとします。左端から始めて、間隔をスキャンします。間隔を入力するたびに、アクティブな間隔の数のカウンターをインクリメントし、1つを離れるたびに、カウンターをデクリメントします。このプロセスの過程でのカウンターの最大値は、探している数値になります。

これを実装するには、間隔のすべての開始点と終了点を（一緒に）長さ2nの巨大なリストに並べ替えます。このリストには、表示されるすべてのセグメントの開始点と終了点が含まれます。次に、リストを左から右にスキャンして、見つけたポイントに基づいてカウンターを更新します（開始ポイントの場合は+1、終了ポイントの場合は-1）。ソートにはO（n log n）時間かかり、スキャンにはO（n）時間かかり、合計でO（n log n）時間かかります。

お役に立てれば！

于 2012-01-23T10:03:19.393 に答える
2

Starts[]とEnds[]に並べ替えます。

i = 0; j = 0; max = 0; total = 0;

while ( i < n ) {
  if ( Starts[i] < Ends[j] ) {
    i++;
    total++;
    if ( total > max ) max = total;
  } else if ( Ends[j] < Starts[i] ) {
    j++;
    total--;
  } else {
    i++;
    j++;
  }
} // while
于 2012-01-23T10:16:13.403 に答える
0
  1. 間隔を開始時刻で並べ替えます。
  2. 終了時刻でソートする優先キューを作成します。
  3. キューに新しい間隔を追加する前に、すべての間隔をポーリングアウトするたびに、これと重複することはありません。

  4. キューのサイズは、一度に重複する間隔になります。

    private Interval solution(Interval[] intervals) {
    Arrays.sort(intervals, (a, b)->{
       return a.start - b.start;
    });

    PriorityQueue<Interval> pq = new PriorityQueue<Interval>((a,b)->{
        return a.end - b.end;
    });

    int start = 0, end = 0;
    int freq = 0;
    for(Interval i: intervals){
        while(!pq.isEmpty() && i.start > pq.peek().end){
          pq.poll();
        }
        pq.offer(i);
        if(pq.size() > freq){
           freq = pq.size();
           start = i.start;
           end = pq.peek().end;
        }
    }
    return new Interval(start, end);
}
于 2017-11-07T07:13:58.737 に答える