debdas
BAN USERI have a solution...
First take an array and initialize all its value to zero...
then for particular interval, increment the array values by one between that interval indices of that array..
for example
(0 5)
increment the values by one between index 0 to index 5.. so we get array[0]=1 array[1]=1....array[5]=1;
then for (2 9) array will be as follows
array[2]=2,array[3]=2,array[4]=2,array[5]=2 array[6]=1...array[9]=1;
as array[2] had a value 1 now it is 2;
for(8 10)
array[8]=2,array[9]=2,array[10]=1;
for(6 9)
array[6]=2,array[7]=2,array[8]=3,array[9]=3;
..after inserting all the values
search the array for the maximum value here it's 3..so the answer will be the corresponding interval...here it is (8 10)..
...the first occurrence of max value will denote the starting time of the maximum overlapping interval...
we can link the interval starting point and end point with corresponding index number...
for array index 0 it will point the interval (0 5)
for array index 2 it will point the interval (2 9)..and so on..
we can use backtracking.....
- debdas April 15, 2014