プログラマ:管制カメラ

(質問リンク)

質問する

高速道路を走るすべての車両が高速道路を使用していると同時に、管制カメラを一度に見られるようにカメラを設置したいと思っています.
高速道路を走行する車両の経路routesをパラメータとして指定した場合、solution関数を完了して、すべての車両に少なくとも何台のカメラを設置すれば一度に管制カメラに遭遇することができるかを返してください.
せいげんじょうけん

車両の数は1台以上10000台以下である.

路線は車両の移動路線[i][0]、路線[i][1]はi次車両が高速道路に進入する場所を含み、路線[i][1]はi次車両が高速道路を離れる場所を含む.

車両の進入点にカメラが取り付けられていても、カメラに遭遇したものとみなされる.

車両の進入点は、−30000以上30000以下である.

I/O例
routesreturn[[-20,-15], [-14,-5], [-18,-13], [-5,-3]]2
I/O例説明
-5時にカメラを設置すると、2台目、4台目の車がカメラに遭遇します.
-15時にカメラを設置すると、1台目と3台目の車がカメラに遭遇します.

に答える

すべての車両が管制カメラに遭遇する最大数は、すべての車両の数である.
車両間に重複する区間がある場合は、カメラを少なく配置してこそ、最小数を求めることができる.
この重なる部分を知ると?
高速道路では、まず場所を離れた車両を並べ替えます.
なぜ宿泊先基準ではなく、外出先基準なのでしょうか?
どの車両が高速道路を出る前に他の車両が入るかが重要なので、出る場所を基準にします.

を出る優先車両から

が並び始める.

車両が高速道路を離れるとき、他の車両と重ならなければカメラ数+1

ソースコード

function solution(routes) {
    // 끝나는 지점이 먼저인 것부터 정렬
    routes.sort((a,b) => a[1] - b[1]);
    
    // 끝나는 지점이 지나는 구간에 안 겹쳤다면 카메라++ & 지점 초기화
    let point = routes[0][1];
    let camera = 1;
    for (let i=1; i<routes.length; i++) {
        if (point < routes[i][0] || routes[i][1] < point) {
            point = routes[i][1];
            camera++;
        }
    }
    return camera;
}