algorithm - 使用线段树查找重叠区间的总长度？

Question

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

PS：我想在不使用段树的情况下这样做，但时间复杂度并不让我满意。

先感谢您

Answer 1

Kobi/Maureinik 的答案非常接近，但我必须为 maxEnd 添加一个变量并检查 differenceFromPrevious 是否为非负数。该算法仍然假设范围在开始元素上排序（即数组[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。

Answer 2

假设间隔存储在数组 [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 位置。