문제 링크

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

문제 설명

• 차량들의 (진입위치, 나간위치) 리스트가 주어진다
• 특정 위치들에 단속 카메라를 설치하여 모든 차량이 한번이라도 지나치도록 함
• 카메라 개수의 최솟값

풀이

• 나간위치로 오름차순 정렬
• 첫번째 차량를 카메라에 담을 수 있으면서 최대한 다른 차량을 커버할 수 있는 위치 => 첫번째 나간위치
• 해당 위치를 지나는 차량들 삭제 (visited = True)
• 삭제되지 않은 차량 중에서 반복

코드

def solution(routes):
    routes.sort(key=lambda x: x[1])
    visited = [False] * len(routes)
    count = 0

    for i in range(len(routes)):
        if not visited[i]:
            visit(routes, visited, routes[i][1])
            count += 1
    return count


def visit(routes, visited, t):
    for i in range(len(routes)):
        s, e = routes[i]
        if s <= t <= e:
            visited[i] = True