단속카메라

• 두 가지의 비슷하지만 조금 다른 그리디 풀이가 있다
• 첫번째 방법은, 진입점이 작은 구간부터 처리하는 방법이다.
  • 진입점 기준으로 구간들을 정렬하고, 순서대로 다음 처리를 해준다. 이전까지의 구간들의 겹치는 구간과 현재 구간과 겹치는 부분이 있다면, 겹치는 구간을 업데이트 해준다. 겹치지 않는다면, 이전까지의 겹치는 구간에 카메라를 설치한다.
  • 첨부된 코드는 이 방식이다.
• 두번째 방법은, 진출점이 작은 구간부터 처리하는 방법이다.
  • 진출점이 작은 순서대로 구간들을 정렬하고 순서대로 처리를 한다. 현재 구간 안에 카메라가 설치되어 있는지 확인하고 (마지막으로 설치된 카메라가 현재 구간 안에 있는지 확인하면 된다), 설치되어 있지 않다면 현재 구간의 진출점에 카메라를 설치한다.
  • 이 방식으로 구현은 안해봤다.
• 두 방법 모두 구간을 정렬한 뒤, 순서대로 읽으며 처리하는 것이라서 시간 복잡도는 O(nlogn)이다. 코드도 둘다 간단하다.

"""Solution code for "Programmers 42884. 단속카메라".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42884
- Solution link: http://www.teferi.net/ps/problems/programmers/42884
"""

INF = float('inf')


def solution(routes):
    answer = 0
    intersect_r = -INF
    for l, r in sorted(routes):
        if l <= intersect_r:
            intersect_r = min(r, intersect_r)
        else:
            answer += 1
            intersect_r = r
    
    return answer