使用线段树找到重叠区间的总长度？

Question

我们有一些区间，例如 [1;4] [7;13] [9;14] ，输入应该返回 3+6+1=10。 当这些区间可以动态插入或删除时，是否有使用线段树的方法来找到这些区间的总长度？

附言：我想过不使用线段树来完成，但时间复杂度不能满足我的需求。

提前感谢您。

- CoderInNetwork

---

你有多少个区间，以及区间的最大最小位置和长度。需要多少次请求来获取总和，需要插入多少次？ - Толя

你的示例中间隔是否已排序？ - Andriy Tylychko

@AndyT 是的，我可以先对它们进行排序。 - CoderInNetwork

间隔可以动态地插入或删除。 - CoderInNetwork

Answer 1

假设这些区间存储在一个数组[m, n]中。 另一个假设是该数组已排序。

你只需要找到较小的差异即可：

 int totalIntervales = 0;
 for(int index = 0; index < array.length ; index++)
 {
     int currentIntrval = array[index, 1] - array[index, 0];
     int differnceFromPrevious = array[index, 1] - array[index- 1, 1]
     totalIntervale += currentIntrval  > differnceFromPrevious ? differnceFromPrevious : currentIntrval;
 }
 return totalIntervale;

仅需小心处理位置0。

- Kobi

---

我认为你的算法在第二个区间完全包含在第一个区间时存在漏洞。考虑集合[1,4][2,3]。你的算法会说这个区间是2。修复方法是检查differenceFromPrevious是否为非负数。否则，它似乎可以工作。（编辑因为我忘记按“回车”提交评论） - James

实际上，经过进一步的思考，我认为你的算法并不是很好。以[1, 5][1, 2][2, 4]为例。你的算法会报告4-3+2=3。 - James

Answer 2

Kobi/Maureinik的答案非常接近，但我必须添加一个maxEnd变量，并检查differenceFromPrevious是否为非负数。该算法仍然假定范围按起始元素（即array [i，0]）排序。

int totalInterval = array[0, 1] - array[0, 0];
int maxEnd = array[0, 1];
for(int index = 1; index < array.length ; index++) {
  int currentIntrval = array[index, 1] - array[index, 0];
  int differnceFromPrevious = array[index, 1] - maxEnd;
  if(differenceFromPrevious >= 0) {
    totalInterval += (currentIntrval > differnceFromPrevious) ? differnceFromPrevious : currentIntrval;
  }
  maxEnd = (maxEnd >= array[index, 1]) ? maxEnd : array[index, 1];
}
return totalInterval;

编辑：修复了意外复制原始totalInterval逻辑的错误。如果differenceFromPrevoius < 0，则应保持totalInterval不变。

- James