Blue Ocean: Total length of overlapping intervals
The original question is here: http://stackoverflow.com/questions/14522808/find-the-total-length-of-overlapped-intervals-using-segment-tree
We have some intervals for example [1;4] [7;13] [9;14] inputs should return 3+6+1=10. Is there any way using segment trees to find the total length of these intervals when the intervals can be dynamically inserted or deleted?
My implementation takes O(n), but if this query is run multiple times and data structure needs to support dynamic insert and delete, O(n) seems not good enough. Is there any O(logN) solution?
public class Interval implements Comparable<Interval>{
int left, right;
public Interval(int l, int r){
this.left = l; this.right = r;
}
@Override
public int compareTo(Interval i){
return this.left - i.left;
}
public boolean overlap(Interval inter){
return this.left <= inter.right && this.right >= inter.left;
}
}
/*
* this implementation assuming static input, use array to present the ordered intervals
* for dynamically input such as add/delete on the fly,
* we can use balanced interval tree, then in-order travel to process the tree
* storage O(n)
* query time O(n)
* construction: O(nlog(n))
* insertion: o(n)
*/
public int totalLength(Interval[] pairs){
//sort by the left corr
Arrays.sort(pairs);
List<Interval> merged = new ArrayList<Interval>();
merged.add(pairs[0]);
for(int i=1; i<pairs.length; i++){
int size = merged.size();
Interval lastInter = merged.get(size-1);
if(lastInter.overlap(pairs[i])){
lastInter.right = Math.max(lastInter.right, pairs[i].right);
}else{
merged.add(pairs[i]);
}
}
int sum = 0;
for(Interval inter : merged){
sum += inter.right - inter.left;
}
return sum;
}
http://stackoverflow.com/questions/14522808/find-the-total-length-of-overlapped-intervals-using-segment-tree 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;