[programmers/py] 단속카메라

단속카메라

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

문제 설명

• 고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

문제 풀이

• 요격 시스템문제와 같은 방식
• 그리디 문제임

def solution(routes):
    answer = 1
    
    if len(routes) == 1:
        return 1
    
    routes.sort(key=lambda x:x[1])
    min_v = routes[0][1]
    
    i = 1
    while i < len(routes):
        s, e = routes[i] # 시작, 끝
        
        # 시작 > min_v
        if s > min_v:
            answer += 1
            min_v = e
            
        i += 1
    
    return answer