首页 > 代码库 > marzullo's algorithm

marzullo's algorithm

given several intervals, how to find a interval which is a intersect of the most number of the given intervals?

Method:

Step1: Represent each returned interval in the following form [start, +1] , [end, -1]
Step2: You now have a list of tuples, the first element of which is a time. Sort these tuples by the time, irrespective of whatever is the second element. So you would have [t(i), val(i)], [t(i+1), val(i+1)], ... where val(i) = ±1. 
Step3: initialize two vars count = 0 and max =0
Step4: Now run through the sorted tuples and set count = count + val(i)
            Compare if count > max then 
                                set max = count
                                set answer = [t(i), t(i+1)]
Step5: Return answer

marzullo's algorithm