https://programmers.co.kr/learn/courses/30/lessons/42884

問題の説明

高速道路を走るすべての車両が高速道路を使用していると同時に、管制カメラを一度に見られるようにカメラを設置したいと思っています.
高速道路を走行する車両の経路をパラメータとして指定すると、すべての車両が一度に取り締まりカメラに遭遇したときに少なくとも何台のカメラを取り付ける必要があるかを返す解関数が完了する.

せいげんじょうけん

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

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

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

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

に答える

グリディが先にソート
ほとんど解き終わったが、なかなか解けないので、答えを見た.
私が初めて解く方法は時間順に並べ替えます.
outを最も低い数字に更新し、
outと現在の自動車の進入時間を比較し、進入時間がoutより高い場合は、答えを追加します.
しかしoutを更新する方法が間違っています.
必ず小さいものを外に置くわけではありません.
進入点がoutより高い場合は取付を行い、outをその車の終点に更新する.
また、次の車の終点がout以下であれば重複するため、outをその車の終点に更新する必要がある.
例:

こんなふうに並んでも

outは5になり、進入点3と比較する
2つのポイントが切れていないので、outは更新できません.カメラを取り付ける必要もありません.

次の車を見てアウトの後ろに入ります
そのため、カメラを追加してoutを更新します.

次の車を見ると、アウトより終点が低いです
そうすると、カメラは取り付けませんがoutが更新されます.

最後の車の入口点はoutより高いので、カメラを取り付けたり、outを更新したりすることができます.
したがって、1つは既にインストールされています(response=1に初期化されています)、もう2つはインストールされています.合計3つ必要です.

def solution(routes):
    answer = 1 # 1개는 무조건 설치 되어있다고 가정
    sortedRoutes = sorted(routes, key=lambda x: x[0]) # 정렬
    out = sortedRoutes[0][1] # 첫번째 차의 끝 지점을 out으로 지정
    for r in sortedRoutes[1:]:
        if r[0] > out: # out보다 현재차의 진입점이 높으면  
            answer += 1 # 카메라 설치하고
            out = r[1] # out 갱신
        if out >= r[1]: # out보다 현재차의 끝지점이 낮으면 겹치는 것이므로
            out = r[1] # out 갱신
    return answer