プログラマ-コントロールカメラPython

4174 ワード
greedy テストアルゴリズム プログラマ python テキストリンク
問題の説明
高速道路を走るすべての車両が高速道路を使用していると同時に、管制カメラを一度に見られるようにカメラを設置したいと思っています.
高速道路を走行する車両の経路をパラメータとして指定すると、すべての車両が一度に取り締まりカメラに遭遇したときに少なくとも何台のカメラを取り付ける必要があるかを返す解関数が完了する.
せいげんじょうけん
  • 車両の数は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台目の車がカメラに遭遇します.
  • 115時にカメラを設置すると、1台目と3台目の車がカメラに遭遇します.
    • 私の答え
    def solution(routes):
    routes.sort(key=lambda x:x[1])
    Q = {i for i in range(len(routes))} #아직 카메라가 찍히지 않은 루트
    answer = 0
    while len(Q) != 0:
        camera = min(Q)
        cameraPoint = routes[camera][1]
        removeList = []
        for route in Q:
            if cameraPoint >= routes[route][0] and cameraPoint <= routes[route][1]:
                removeList.append(route)
        for item in removeList:
            Q.remove(item)
        answer += 1
    return answer
    Feedback
    学校の「アルゴリズム」の授業で学んだことが手伝ってくれました.Greedyアルゴリズム部分で会議室を最大限に利用するアルゴリズムを学習した.これは会議室の使用終了順に並べ替えて解決する方法であり,そこからインスピレーションを得た.会議室の手配はできるだけ重ねないようにし、管制カメラはできるだけ重ねなければならないので、似たような方法で解決すればいい.
    ASP.NET実践:プログラミングアクセスASP.NET設定
    プログラマーポケモンjava