查找重叠间隔坐标的复杂度降低

此代码返回重叠坐标。示例：输入[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 - 当然你很聪明，可以自己解决:-) –

查找重叠间隔坐标的复杂度降低

回答

相关问题