Skip to content

Instantly share code, notes, and snippets.

@sspencer
Created June 3, 2015 01:02
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save sspencer/f0f1f4466a0239eb61e1 to your computer and use it in GitHub Desktop.
Save sspencer/f0f1f4466a0239eb61e1 to your computer and use it in GitHub Desktop.
Marzullo's algorithm in JavaScript based on http://vmaroli2.blogspot.com/2012/11/marzullos-algorithm-in-java.html
// MarzulloAlgorithm in JavaScript
//
// Not quite what I need which is a list of ranges that contain a specified number.
//
'use strict';
function Point(name, point, type) {
this.name = name;
this.point = point;
this.type = type;
}
function Range(name, start, end) {
this.name = name;
this.start = start;
this.end = end;
}
function marzullo(ranges) {
var best = 0;
var count = 0;
var beststart = 0;
var bestend = 0;
var i = 0;
var name = "";
var points = [];
ranges.forEach(function(r) {
points.push(new Point(r.name, r.start, -1));
points.push(new Point(r.name, r.end, 1));
});
points.sort(function(a, b) {
return (a.point - b.point) || (b.type - a.type);
});
points.forEach(function(p) {
count = count - p.type;
if(best < count) {
   best = count;
   beststart = p.point;
   if (i < points.length-1) {
    bestend = points[i+1].point;
name = p.name + "," + points[i+1].name;
}
}
i++;
});
return new Range(name, beststart, bestend);
}
var ranges = [
new Range("r1", 10, 40),
new Range("r2", 30, 50),
new Range("r3", 35, 45),
];
console.log(marzullo(ranges));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment