Skip to content

Instantly share code, notes, and snippets.

@renso3x
Created October 7, 2019 14:42
Show Gist options
  • Save renso3x/9429a5c3f093d2218e5cf75db3abb82f to your computer and use it in GitHub Desktop.
Save renso3x/9429a5c3f093d2218e5cf75db3abb82f to your computer and use it in GitHub Desktop.
Object.defineProperty(Array.prototype, "first", {
get: function() {
return this[0];
}
});
Object.defineProperty(Array.prototype, "last", {
get: function() {
return this[this.length - 1];
}
});
const getSkyline = buildings => {
return helper(buildings, 0, buildings.length - 1);
};
const helper = (buildings, lo, hi) => {
if (lo > hi) {
return [];
}
if (lo === hi) {
return [[buildings[lo][0], buildings[lo][2]], [buildings[lo][1], 0]];
}
const mid = lo + Math.floor((hi - lo) / 2);
const left = helper(buildings, lo, mid);
const right = helper(buildings, mid + 1, hi);
let h1 = 0;
let h2 = 0;
const result = [];
while (left.length && right.length) {
let x, h;
if (left.first[0] < right.first[0]) {
[x, h1] = left.shift();
} else if (left.first[0] > right.first[0]) {
[x, h2] = right.shift();
} else {
[x, h1] = left.shift();
[x, h2] = right.shift();
}
h = Math.max(h1, h2);
if (result.length === 0 || result.last[1] != h) {
result.push([x, h]);
}
}
while (left.length) {
result.push(left.shift());
}
while (right.length) {
result.push(right.shift());
}
return result;
};
const testCases = [
[[], []],
[[[0, 2, 3], [2, 5, 3]], [[0, 3], [5, 0]]],
[[[1, 2, 1], [1, 2, 2], [1, 2, 3]], [[1, 3], [2, 0]]],
[
[[2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8]],
[[2, 10], [3, 15], [7, 12], [12, 0], [15, 10], [20, 8], [24, 0]]
]
];
testCases.forEach(([buildings, expected], index) => {
getSkyline(buildings);
});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment