Marzullo's algorithm, invented by Keith Marzullo for his Ph.D. dissertation in 1984, is an agreement algorithm used to select sources for estimating accurate time from a number of noisy time sources. I was working on similar requirement at work and came across the algorithm in Wikipedia. Here is a Java implementation of the algorithm.
I have added some data structures like Range and Point for my purpose at work. Definition for Range and Point below.
public class MarzulloAlgorithm { public static void main(String[] args) { Range r1 = new Range("1",10,40); Range r2 = new Range("2",30,50); Range r3 = new Range("3",35,45); List<range> ranges = new ArrayList<range>(); ranges.add(r1); ranges.add(r2); ranges.add(r3); MarzulloAlgorithm m = new MarzulloAlgorithm(); Range r = m.marzulloAlgorithm(ranges); } public Range marzulloAlgorithm (List<range> ranges) { Range result = null; int best = 0; int count = 0; int beststart = 0; int bestend = 0; int i = 0; String name = ""; List<point> points = new ArrayList<point>(); for(Range r:ranges) { points.add(new Point(r.getName(),r.getStart(),-1)); points.add(new Point(r.getName(),r.getEnd(),+1)); } Collections.sort(points,new PointComparator()); for(Point p:points) { count = count - p.getType(); if(best < count) { best = count; beststart = p.getPoint(); if(i<(points.size()-1)) { bestend = points.get(i+1).getPoint(); name = p.getName() + "," + points.get(i+1).getName(); } } i++; } result = new Range(name,beststart,bestend); return(result); } }
I have added some data structures like Range and Point for my purpose at work. Definition for Range and Point below.
public class Point { String name; int point; int type; public Point(String name, int point, int type) { this.name = name; this.point = point; this.type = type; } public String getName() { return name; } public int getPoint() { return point; } public int getType() { return type; } }
public class Range { String name; int start; int end; public Range(String name, int start, int end) { this.name = name; this.start = start; this.end = end; } public String getName() { return name; } public int getStart() { return start; } public int getEnd() { return end; } }