[プログラマー]貪欲法(Greedy)-管制カメラ(Level 3)

せいぎょカメラ
解法

のカメラは、設置されたカメラを最小限に抑えるために、できるだけ多くの車両が必要です.

の路線リストを進入地点を基準に並べ替えます.

カメラは、最も多くの車両に遭遇する区間の始点と終点をstart変数とend変数としてそれぞれ記憶する.start変数は−30000に初期化され、end変数は30000に初期化された.

路線リストを送信します.startを現在の車両の進入点に更新します.この更新のstartがendより大きい場合、1つのカメラで上書き可能な区間が終了するので、答えに1を加え、endを現在の車両のインバウンドサイトに更新します.そうでなければ、endは、現在の車両のインバウンドがendより小さい場合にのみ、現在の車両のインバウンドに更新される.最後の段落にカメラが付いていない部分があるので、回答ではプラス1の値を返します.
ex.ルーティング=[-20,15],[-18,13],[-14,-5],[-5,3]の場合、カメラを取り付ける必要がある区間は[14,-13],[-5,3]である.上記のように[14,-13]区間を求め,for文が[-5,3]車両に移行すると,1つのカメラで上書きすることができなくなるため,答えに1を加える.[-5,3]車両の次の車両がないため、for文では[-5,3]セグメント追加カメラの部分は実行されないので、最後に答えに1を追加します.

Python Code

def solution(routes):
    answer = 0

    routes.sort(key=lambda x:x[0])
    print(routes)
    
    start = -30000
    end = 30000
    for i in routes:
        start = i[0]
        if start>end:
            answer += 1
            end = i[1]
        if i[1]<end:
            end = i[1]
        
    return answer+1

エラーと解決
集合オーバーライド問題を用いて解いてみたがタイムアウトしたのでfor文の上の方法を変えた.