[프로그래머스/42884/level3/고득점kit] 단속 카메라 - 그리디

문제

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

내 풀이 

3가지 경우의 수 존재

1. 두 경로가 서로 포함관계 일경우 - 진출지점이 더 작은 값인 쪽에 설치(=짧은 경로)

2. 일부분이 겹치는 경우 - 진출지점이 더 작은 값인 쪽에 설치

3. 아예 안겹치는 경우 - 따로따로 설치

'''
    3가지 경우의 수 존재
    1. 두 경로가 서로 포함관계 일경우 - 진출지점이 더 작은 값인 쪽에 설치(=짧은 경로)
    2. 일부분이 겹치는 경우 - 진출지점이 더 작은 값인 쪽에 설치
    3. 아예 안겹치는 경우 - 따로따로 설치
'''
    
def solution(routes):
    #진출 지점이 작은 값부터 정렬
    routes.sort(key = lambda x: x[1])
    
    # 첫번째 경로의 도착지점에 카메라 설치함을 가정하고 시작
    answer = 1 
    pre_camera = routes[0][1] 
    
    #[i번째 차량이 고속도로에 진입한 지점, 나간 지점]
    for s, e in routes:
        # 이전 카메라 설치 지점과 시작지점이 겹치지 않으면 새로 설치
        if pre_camera < s:
            answer += 1
            pre_camera = e
    
    return answer