Sign in Subscribe
Technology

Gridland Metro

Merge overlapping tracks to keep it disjoint.

Gridland Metro

Problem

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

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]) {
    before.push(tracks[i++]);
  }
  while (i < tracks.length && reference[0] <= tracks[i][1]) {
    middle.push(tracks[i++]);
  }
  while (i < tracks.length) {
    after.push(tracks[i++]);
  }
  return [before, middle, after];
}

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

Read next