Editing Marzullo's algorithm (section)

==Method==

Marzullo's algorithm begins by preparing a table of the sources, sorting it and then searching (efficiently) for the intersections of intervals.  For each source there is a range [c&minus;r,c+r] defined by c&nbsp;±&nbsp;r. For each range the table will have two [[tuple]]s of the form {{angbr|offset,type}}. One tuple will represent the beginning of the range, marked with type &minus;1 as {{angbr|c&minus;r,&minus;1}} and the other will represent the end with type +1 as {{angbr|c+r,+1}}.

The description of the algorithm uses the following variables: best (largest number of overlapping intervals found), cnt (current number of overlapping intervals), beststart and bestend (the beginning and end of best interval found so far), i (an index), and the table of tuples.

# <li value="0">Build the table of tuples.</li>
# [[sorting algorithm|Sort]] the table by the offset.  (If two tuples with the same offset but opposite types exist, indicating that one interval ends just as another begins, then a method of deciding which comes first is necessary.  Such an occurrence can be considered an overlap with no duration, which can be found by the algorithm by putting type &minus;1 before type +1. If such pathological overlaps are considered objectionable they can be avoided by putting type +1 before &minus;1 in this case.)
# [initialize] best=0 cnt=0
# [loop] go through each tuple in the table in ascending order
:# <li value="4">[current number of overlapping intervals] cnt=cnt−type[i]</li>
:# if cnt>best then best=cnt beststart=offset[i] bestend=offset[i+1]

:''commentary: the next tuple, at [i+1], will either be an end of an interval (type=+1) in which case it ends this best interval, or it will be a beginning of an interval (type=&minus;1) and in the next step will replace best.''

:''ambiguity: unspecified is what to do if best=cnt.  This is a condition of a tie for greatest overlap.  The decision can either be made to take the smaller of bestend&minus;beststart and offset[i+1]&minus;offset[i] or just take an arbitrary one of the two equally good entries. This decision is relevant only when type[i+1]=+1.''

# <li value="6">[end loop] return [beststart,bestend] as optimal interval.  The number of ''false'' sources (ones which do not overlap the optimal interval returned) is the number of sources minus the value of best.</li>