如何找到這些具有共同點的間隔的最大數量？

我一直在審查的算法，這是來自Anany列維京的算法中書的問題..如何找到這些具有共同點的間隔的最大數量？

您在有n個開區間的列表（A1，B1），...，（一，BN）真正的路線。（開放間隔（a，b）包括其端點a和b之間嚴格爲的所有點，即（a，b）=（xi a < x < b}。）找到這些間隔的最大數量例如，對於示例，對於間隔（1,4），（0,3），（-1.5,2），（3.6,5），此最大數爲3.設計此問題的算法，一個比二次時效性更好。

任何一個可以幫助我形成了它的算法或在互聯網上提出任何資源..

謝謝， Hareendra

來源

2012-01-23 hareendra reddy

你想知道*任何*算法，或者一個比二次的時間複雜度更好，因爲在您的報價中提到？ –

嗨BjörnPollex，我需要一個更好的算法，我可以框架暴力解決這個.. –

是這個功課？ – soulcheck

解決此問題的一種方法如下：假設您要排列實數行上的所有間隔。從最左側開始掃描間隔。每次輸入一個間隔時，增加一個活動間隔數的計數器，並且每次您離開一個計數器時遞減計數器。在這個過程中計數器的最大值就是你要查找的數字。

要實現這一點，將間隔（一起）的所有開始點和結束點分類爲長度爲2n的巨大列表，其中包含所有段出現時的開始點和結束點。然後，從左到右掃描列表，根據找到的點更新計數器（起點爲+1，終點爲-1）。排序需要O（n log n）時間，掃描需要O（n）時間，總共需要O（n log n）時間。

希望這會有所幫助！

來源

2012-01-23 10:03:19 templatetypedef

掃描需要O（n）我認爲。 – jgroenen

@ jgroenen-哎呀......這絕對不是我的意思！讓我解決這個問題...... – templatetypedef

而且因爲間隔是開放的，所以在排序點的時候會有一個打破平局的問題，如下所示：如果兩個端點具有相同的值，那麼在開始點之前排序結束點*。 –

分爲開始[]和結束[]。

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-23 10:16:13 jgroenen

排序間隔由起始時間。
通過結束時間創建優先級隊列排序。
每次在向隊列中添加一個新的時間間隔之前，輪詢出所有的時間間隔與此沒有重疊。

隊列大小將是一次重疊的時間間隔。

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-07 07:13:58

如何找到這些具有共同點的間隔的最大數量？

回答

相關問題