-1

可能重复：
区间联合
如何有效地重叠区间

给定一个区间列表表示所有整数，如果它们确实相交或重叠，则应该可以将它们折叠成一个区间，否则给定的区间不受影响。比如说，如果输入是 egI [(2-6), (1-4), (8-12)]，那么预期的输出是 [(1-6), (8-12)] eg II [(4- 7), (2-6), (1-4), (8-12), (7-9)] 预期的输出是 [(1-12)]。

更正：错过了排序部分，所以是的，它是 O(nlogn) 时间而不是 O(n)。感谢您指出了这一点。我已经编写并测试了一个有效的 O(nlogn) 时间和 O(2n) 空间算法方法。在下面分享这种方法的代码。我有兴趣听到解决这个问题的不同方法，可能更有效。

//假设每个区间，(2-6)等都表示为“Interval”对象（类定义如下图），其中low = 2 and high = 6 // Step1：按给定的低端点排序间隔 // Step2：找到排序间隔的并集

//输入：

List<Interval> intervalList = new ArrayList<Interval>();

//输出：

List<Interval> unionList = new ArrayList<Interval>();    

private static final Comparator<Interval> Low_EPSorter = new LowEPSorter();

class Interval {
  int low, high;

  Interval(int l, int h, int m) {
    low = l;
    high = h;
  }
}

////-------BEGIN：找到给定区间的并集的方法----//////

void UnionOfIntervals() {
  //Find intersection and combine intervals as necessary
  int sz = intervalList.size();

  // sort by low endpoint
  Collections.sort(intervalList, Low_EPSorter);

      for(int i = 0; i < sz; i++) {
        int j = i;
        if(j > 0) {
          if( Intervals.intersect(intervalList.get(j), intervalList.get(j-1)) ) {
            Interval v = union(intervalList.get(j), intervalList.get(j-1));
            checkAndAdd(v, unionList);
          }
          else {
            if(i == 1) {
              unionList.add(intervalList.get(j-1));
              unionList.add(intervalList.get(j));
          }
          else {
            unionList.add(intervalList.get(j));
          }
        } //No intersection
      } //If 2 elements atleast
      }

      //Print intervals after union
      System.out.println("Input intervals after sorting:");
      for(Interval v : intervalList) {
        System.out.print(v.low + "," + v.high + " ");
      }
      System.out.println();
      System.out.println("Union of intervals:");
      for(Interval v : unionList) {
        System.out.print(v.low + "," + v.high + " ");
      }
    }

    void checkAndAdd(Interval x, List t) {
      int top = t.size()-1;
      if( top >=0 && Intervals.intersect(unionList.get(top), x) ) {
        Interval v = union(unionList.get(top), x);
        t.remove(top);
        t.add(v);
      }
      else {
        t.add(x);
      }
    }

////-------END：找到给定区间的并集的方法----//////

////--- 辅助方法 --- ////

static boolean intersect(Interval a, Interval b) {
      boolean r = false;
      if(b.high < a.low || b.low > a.high)
        r = false;
      else if(a.low <= b.high && b.low <= a.high)
        r = true;
      return r;
}

Interval union(Interval a, Interval b) {
      int l = (a.low < b.low) ? a.low : b.low;
      int max = (a.high > b.high) ? a.high : b.high;
      return new Interval(l, max);
}

private static class LowEPSorter implements Comparator<Interval> {

      public int compare(Interval a, Interval b) {
        int r = 0;
        if(a.low < b.low)
          r = -1;
        else if(a.low > b.low)
          r = 1;
        return r;
      }

}
4

4 回答 4

1

取一个大小为 n 的数组（其中 n 是最大数），并分别用 1 和 -1 填充区间开始和结束。

我的意思是如果间隔是

{[1-4],[6-8]}

然后数组元素就像

array[1]=1,array[4]=-1,array[6]=1,array[8]=-1

其余所有其他数组位置将设置为零。

现在遍历数组并通过扫描数组，我们可以获得间隔，就像这种情况一样

{[1-4],[2-5],[7-9]},

首先如上所述填充数组，数组 A 看起来像（假设起始索引为 1）：

A=[1,1,0,-1,-1,0,1,0,1]

现在从头开始遍历数组 A 并取一个变量 sum=0 并将存储在数组位置的值添加到 sum 中。

说明数组每个索引处的总和：

在位置 1: sum = 1 ( 1 at index 1 )

在位置 2: sum = 2 ( 1 at index 2 )

在位置 3: sum = 2 ( 0 at index 3 )

在位置 4: sum = 1 ( -1 at index 4 )

在位置 5：sum = 0（索引 5 处的 -1）

现在总和达到零，这意味着间隔在这里结束，所以新的间隔将是 [1-5]

在位置 6：sum = 0（索引 6 处为 0）

在位置 7：sum = 1（索引 7 处的 1）

（在位置 7，总和再次大于零，这意味着间隔刚刚开始）

在位置 8：sum = 1（索引 8 处为 0）

在位置 9：sum = 0（索引 9 处的 -1）

从位置 7 开始的时间间隔刚刚结束，因此新的时间间隔范围为

{[1-5],[7-9]}

希望能帮助到你。

于 2012-09-11T19:21:53.970 回答
0

如果你正在为这个问题寻找比 O(n) 更有效的算法，我不相信你会找到它。无论您使用什么数据结构来存储初始间隔值，最坏的情况是没有一个间隔重叠，您必须检查每个间隔以确认这一点，因此 O(n)。即使有HashMap一个非常复杂的密钥结构，你仍然在看 O(n)。

话虽如此，我不确定是否有任何其他方法值得研究，因为您已经找到了一种可以在最佳时间 O(n) 解决它的算法。

于 2012-09-10T17:22:55.070 回答
0

只是一个想法：管理一组不相交的间隔。从空集开始，添加传入间隔。如果新区间与一个或两个现有区间相交，请将它们合并。要计算交点，请使用 2 个 TreeMap 引用同一组区间但使用不同的键：下限和上限。

于 2012-09-10T17:23:48.017 回答
0

只是另一个想法：

  • 使用布尔数组
    • 默认情况下将所有值设为 false
    • 对于所有间隔（输入）使值为真
    • 扫描更新后的数组，得到最终的相交结果。
于 2012-09-10T17:42:54.797 回答