查找重疊間隔座標的複雜度降低

此代碼返回重疊座標。示例：輸入[10，30] [20，50] [40，70，] [60，90] [80，100] 答案應該是：[20,30]，[40,50] [ 60,70] [80,90] 有沒有辦法解決這個問題的時間複雜度小於二次方？查找重疊間隔座標的複雜度降低

謝謝，

public static Set<OverlapCoord> getOverlap(List<Interval> intervalList) { 
    if (intervalList == null) { 
     throw new NullPointerException("Input list cannot be null."); 
    } 

    final HashSet<OverlapCoord> hashSet = new HashSet<OverlapCoord>(); 

    for (int i = 0; i < intervalList.size() - 1; i++) { 
     final Interval intervali = intervalList.get(i); 

     for (int j = 0; j < intervalList.size(); j++) { 
      final Interval intervalj = intervalList.get(j); 

      if (intervalj.getStart() < intervali.getEnd() && intervalj.getEnd() > intervali.getStart() && i != j) { 
       hashSet.add(new OverlapCoord(Math.max(intervali.getStart(),intervalj.getStart()), 
              Math.min(intervali.getEnd(), intervalj.getEnd()))); 
      } 
     } 
    } 

    return hashSet; 
}

來源

2013-08-05 JavaDeveloper

是否有可能超過兩個區間重疊？ – Akinakes

是的，允許重疊。 – JavaDeveloper

您可以通過排序間隔陣列，以此降低到O(NlogN)然後再遍歷它比較連續的時間間隔（由間隔開始點排序）。

我懷疑是否有可能做得更好O(NlogN)除非您可以分攤多個運行的排序步驟的成本。

請注意，如果一個間隔可以重疊多於一個其他間隔，則此一般方法將起作用。但是如果你想枚舉每一個重疊，那麼在最壞的情況下可能會有O(N^2)重疊，因此算法必須是O(N^2)。（例如，在「[1,2]，[1,2]，[1,2]，[1,2]」中，每個區間重疊所有其他區域，給出6個重疊...或者12個if你不消除對稱對。）

來源

2013-08-05 01:55:09

一個僞代碼會有所幫助，謝謝 – JavaDeveloper

@JavaDeveloper - 當然你很聰明，可以自己解決:-) –

查找重疊間隔座標的複雜度降低

回答

相關問題