skyline

Divide and conquer algorithm to solve "The Skyline Problem".

Demo

https://lab.miguelmota.com/skyline

Install

npm install skyline

Usage

Input is a squence of building triples: left x-coordinate, height y-coordinate, right x-coordinate.

Output is a sequence of skyline tuples: left x-coordinate, height y-coordinate.

const skyline = require('flowright');

const buildings = [
  [1,11,5],
  [2,6,7],
  [3,13,9],
  [12,7,16],
  [14,3,25],
  [19,18,22],
  [23,13,29],
  [24,4,28]
];

var skylinePoints = skyline(buildings);
console.log(skylinePoints);
//
[
  [1,11],
  [3,13],
  [9,0],
  [12,7],
  [16,3],
  [19,18],
  [22,3],
  [23,13],
  [29,0]
]

Test

npm test

Credit

This C solution

License

MIT