Gridland Metro

Merge overlapping tracks to keep it disjoint.

Gridland Metro


Gridland Metro | HackerRank
Help the mayor determine the potential locations for lampposts!

How to Solve

This problem can be solved by concatenating overlapping tracks.

type Line = [number, number];
function categorize(reference: Line, tracks: Line[]): [Line[], Line[], Line[]] {
  const [before, middle, after]: [Line[], Line[], Line[]] = [[], [], []];
  let i = 0;
  while (i < tracks.length && reference[1] < tracks[i][0]) {
  while (i < tracks.length && reference[0] <= tracks[i][1]) {
  while (i < tracks.length) {
  return [before, middle, after];

For JS/TS folks: do not forget to use bigint when you calculate the total number of cells.