[Programmers] 단속 카메라

단속 카메라

단속 카메라 를 클릭하면 바로 이동한다.

그리디는 진짜 어렵다.. 바로 이전에 푼 문제도 그리디였다.. 그리디 문제를 골라서 좀 풀어봐야겠다.

이 문제는 우선 나간 지점이 빠른 순으로 정렬을 해야한다.

그리고 먼저 나간 차의 나간 지점에 CCTV를 설치하고 시작한다.

그리고 그 다음 차의 진입 지점이 현재 CCTV 설치 지점 보다 크면 CCTV를 설치하고 CCTV 위치를 갱신한다.

---

def solution(routes):
    routes.sort(key=lambda x: x[1])
    answer = 1
    CCTV = routes[0][1]

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

    return answer


if __name__ == "__main__":
    routes = [[-20, 15], [-14, -5], [-18, -13], [-5, -3]]
    print(solution(routes))