[Python] 단속카메라

1. 문제

 

 

 

2. 풀이 방법

방법 1) 시작점을 기준으로 오름차순 정렬

def solution(routes):
    answer = 0
    routes.sort()
    s = -300000
    e = 30000
    for route in routes:
    	#범위에 교집합이 있으면 범위를 교집합으로 설정
        if s <= route[0] <= e or s <= route[1] <= e:
            s = max(s, route[0])
            e = min(e, route[1])
        else: #범위를 벗어나면 그 전 범위에 카메라 설치하고 범위 다시 세팅
            answer += 1
            s = route[0]
            e = route[1]
    #마지막 범위에 카메라 설치 : + 1
    return answer + 1

 

방법 2) 끝 지점을 기준으로 오름차순 정렬, 간결함

def solution(routes):
    answer = 0
    routes.sort(key = lambda x : x[1])
    camera = -30001 #새로 추가한 카메라의 위치
    
    for route in routes:
        if camera < route[0]:
            answer += 1
            camera = route[1]
    return answer