Geek asks and answers

Find the total length of overlapping intervals using the segment tree?

We have some intervals, for example [1; 4] [7; 13] [9; 14]. Inputs should return 3 + 6 + 1 = 10. Can segment trees be used to find the total length of these intervals when the intervals can be dynamically inserted or deleted?

PS: I thought about it without using the segment tree, but the time complexity does not satisfy me.

early

+5
source share
2 answers

suggests that the intervals are stored in the [m, n] array. another assumption is that the array is sorted.

all you have to do is find the smaller difference:

 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;

just handle location 0 carefully.

0

Kobi/Maureinik , maxEnd , FromPrevious . - , start (.. 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, . FromPrevoius < 0, totalInterval .

0

More articles:


All Articles