think like this...
create an array [m-n] where m is minimum a in all intervals (a,b) and n is maximum b in all intervals (a,b)
initialize that with 0
from onwards read the intervals...increase the value of array element if index is in that interval
at last...to find all intervals with maximum number range
in example
final array like this
1 2 3 3 3 2 1 1
now result is (3 , 5) ...
i think this solution complexity is O(n) and space complexity is also O(n)
On 8/12/06,
[EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
Given a set of intervals, (a,b)s some of which could have overlap, what
is the best way to find the common sub-interval which overlaps most
number of intervals (a,b) ? There could be more than one such
sub-interval and algo should return all such sub-intervals. For
example,
(1, 5), (2, 6), (3, 8) have (3,5) as the answer.
thanks
dhiman
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
