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 はそのままにしておく必要があります。