カメラ

3890 ワード
アルゴリズム#アルゴリズム# コーディングテスト プログラマ テキストリンク

1.質問


質問リンク
説明:
高速道路を走るすべての車両が高速道路を使用していると同時に、管制カメラを一度に見られるようにカメラを設置したいと思っています.
高速道路を走行する車両の経路をパラメータとして指定すると、すべての車両が一度に取り締まりカメラに遭遇したときに少なくとも何台のカメラを取り付ける必要があるかを返す解関数が完了する.
せいげんじょうけん
  • 車両の数は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台目の車がカメラに遭遇します.

    2.解答


    このような問題は通常最適な解を求める時、
    取り締まりカメラを一番左に貼るか、一番右に貼るかで、感覚が見つかります.
    しかし、常識的にはできるだけ右側に取り付けるべきで、最適な年が保障されていることを直感的に知ることができます.
    そうすれば、できるだけ多くの車両を監視することができます.
    私の説明の仕方はこうです.
  • 車両を高速道路を離れた場所に昇順に並べます.
  • の前から見て、カメラを取締していない区間に遭遇した場合は、車両が離れた場所に取締カメラを設置してください.

    • 3.完全なコード

    function solution(routes) {
    let ans = 0;
    let last_position = -30001; // 마지막으로 설치한 단속 카메라 위치

    // 1. 차량들을 고속도로에서 나간 지점을 기준으로 오름차순 정렬합니다.
    routes.sort((a, b) => a[1] - b[1]);

    // 2. 앞에서부터 보며, 단속 카메라가 없는 구간을 만나면 해당 차량이 나간 지점에 단속 카메라를 설치합니다.
    routes.forEach((route) => {
        if (route[0] > last_position) {
            last_position = route[1];
            ans++;
        }
    });

    return ans;
}
    配列から重複を削除するショート＆甘い方法!
    Git 基本の用語集