0

此代码返回重叠坐标。示例：对于 [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;
}
4

1 回答 1

0

您应该能够O(NlogN)通过对区间数组（按区间起点排序）进行排序，然后通过比较连续区间对其进行迭代来减少这种情况。

我怀疑是否有可能做得更好，O(NlogN)除非您可以在多次运行中分摊排序步骤的成本。

请注意，如果一个区间可以与另一个区间重叠，则此通用方法将起作用。但是如果你想枚举每个重叠，那么在最坏的情况下可能会有O(N^2)重叠，因此算法必须是O(N^2).

（例如，在 "[1,2], [1,2], [1,2], [1, 2]" 中，每个区间都与所有其他区间重叠，给出 6 个重叠......如果不重叠，则为 12 个消除对称对。）

于 2013-08-05T01:55:09.587 回答