Skip to content

Instantly share code, notes, and snippets.

@beyond-code-github
Created April 17, 2024 08:47
Show Gist options
  • Save beyond-code-github/40ded7054ffe91168b3f2ca4f5c17d9f to your computer and use it in GitHub Desktop.
Save beyond-code-github/40ded7054ffe91168b3f2ca4f5c17d9f to your computer and use it in GitHub Desktop.
Use min-heap to find lowest range spanning four lists - Javascript
"use strict";
const Heap = require("heap")
const input = [
[3, 6, 8, 10 , 15],
[1, 5, 12],
[4, 8, 15, 16],
[2, 6]
]
const h = new Heap((a, b) => a.v - b.v);
input.forEach((list, idx) => h.push({v: list.shift(), idx}));
let current;
let ranges = [];
let exhausted = false;
let highest = Math.max(...h.toArray().map(_ => _.v));
while (!exhausted) {
current = h.pop();
ranges.push([current.v, highest]);
const v = input[current.idx].shift();
if (v) {
highest = Math.max(highest, v);
h.push({v, idx: current.idx});
continue;
}
exhausted = true;
}
console.log(ranges)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment