管制カメラ(欲張り)

質問する

質問リンク

私の答え

優先ルートを最初のインデックスでソートしました.つまり、高速道路に入る場所は快速順に並んでいます.

in/out変数を使用して範囲を追跡します.
すなわち、-20~-4は以前の値であり、->13と6が次の値であれば->13と-4はそれぞれin、outに格納される.

の論理は、ルーティングが存在するまで継続され、回転するたびにin、outが初期化される.

def solution(routes):
    #1) sort
    routes = sorted(routes, key  = lambda x:x[0])  # 뒷걸음질....
    answer = 0
    
    while routes:
        # 2) cnt는 제거해야하는 index를 tracking 할 것이다.    
        cnt = 0
        i = routes[0][0]
        o = routes[0][1]
        
        for car in routes:
            if ( i <= car[0] and car[0] <= o) or ( o <= car[1] and car[1] <= o) :
                # in을 둘 중 작은 값으로
                i = car[0] if car[0] > i else i
                # out을 둘 중 큰 값으로
                o = car[1] if o > car[1] else o
                cnt += 1
        routes = routes[cnt:]
        answer += 1
    
    return answer

他人の解答

解けて本当に楽しかったです.でも...

def solution(routes):
    routes = sorted(routes, key=lambda x: x[1])
    last_camera = -30000

    answer = 0

    for route in routes:
        if last_camera < route[0]:
            answer += 1
            last_camera = route[1]

    return answer

??????????????????????????????????????????????????
上のコードは外に出る位置を基準にしています.
そこで、最初の車の出位置(最小値)にカメラを取り付け、カメラに掛けた車が飛び越え、
高速道路に進入する位置が対応するカメラより遅い場合、その車の出口位置にカメラを設置する.
kia~