Skip to content

Instantly share code, notes, and snippets.

@johnwalley
Last active May 19, 2016 10:56
Show Gist options
  • Save johnwalley/4b550358e35aa4f9124eeb81e0217a8e to your computer and use it in GitHub Desktop.
Save johnwalley/4b550358e35aa4f9124eeb81e0217a8e to your computer and use it in GitHub Desktop.
function kingdomAndTrees(a, maxX) {
var lo = 1;
var hi = maxX;
var mid;
while (lo < hi) {
mid = Math.floor((hi + lo)/2);
var success = hasSolution(a, mid);
if (success) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
function hasSolution(a, j) {
var lastHeight = 0;
var i;
for (i = 0; i < a.length; i++) {
if (a[i] + j > lastHeight) {
lastHeight = Math.max(lastHeight + 1, a[i] - j);
} else {
return false;
}
}
if (i === a.length) {
return true;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment