Lv.さんかんカメラ

問題の説明

データ構造

answer

タイプ:整数

ストレージデータ:モニタカメラ数

解法

図中では上図のように、各車両の出入り点がどこにあるかが重要です.
そのため、入場地点を基準に昇順に並びます.

routes = [[-20,-15], [-14,-5], [-18,-13], [-5,-3]]

=>
 
routes = [[-20,-15], [-18,-13], [-14,-5], [-5,-3]]

現在,for文やreduceなどを用いてルーティングの各要素を迂回し,以下の確認を行う.

最初のカメラは最初の車の入場点に置かれています.
->カメラは-15に1つあります.

新しく来た車の進入点は-15の前にありますか?
->-18は-15までなので、-15に取り付けられたカメラで撮影できます.
->前の場合は

に進みます
2-1. 新しく来た車の入り口は-15の後ろにありますか?
->-14は-15以降なので、-15に取り付けられたカメラでは撮影できません.
->カメラをもう一つ取り付けましょう.カメラ位置は今回入った車[14,-5]の入場点-5に置かれている.

このような過程を繰り返すと解決します.

コード実装(JavaScript)

function solution(routes) {
  routes.sort((a, b) => a[1] - b[1]);
  let answer = 1;
  routes.reduce((acc, cur) => {
    if (cur[0] > acc) {
      answer++;
      acc = cur[1];
    }
    return acc;
  }, routes[0][1]);
  return answer;
}

ソース:プログラマ