단속카메라 (Python)

문제 접근

1. (그리디) routes 배열을 제일 빨리 끝나는 순으로 정렬을 하고 생각해보자. 하나의 차량이 고속도로를 빠져나가기 직전 순간에, 그 차량과 함께 달리고 있는 모든 차량들을 단속 카메라로 찍으면 매 순간마다 최적의 답을 찾는 셈이다.
2. (정렬) 빨리 끝나는 순으로 정렬을 할 뿐만 아니라, 함께 끝나는 차량 중에서도 더 빨리 진입하는 차량을 우선으로 배치해야 한다. 동일한 시간에 끝나는 차량이지만 어떤 차는 일찍 고속도로에 진입할 수 있기 때문에, 그 전에 미리 달리던 차량이 이탈했을 경우 함께 이탈시켜야 한다.

코드

def solution(routes):
    routes.sort(key=lambda a: [a[1], a[0]])
    answer = 0
    pointer = 0
    start, target_end = routes[0]
    while True:
        while pointer < len(routes):
            start = routes[pointer][0]
            if start > target_end: break
            target_end = min(target_end, routes[pointer][1])
            pointer += 1
        answer += 1
        if pointer >= len(routes): break
        start, target_end = routes[pointer]
    return answer