[그리디] 단속 카메라

문제 설명

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

프로그래머스

문제 풀이

1. routes에 대한 정렬을 진입,진출 중 어떤 것으로 할 지 선택해야함
2. 진출로 잡아야 해당 차량이 이동하는 구간에서의 카메라 위치를 잡을 수 있음.
3.  현재 차량의 진입 시점이 카메라보다 크다면 그 카메라는 지금의 차량을 잡을 수 없으므로 카메라를 하나 더 추가해야함
4. 그 카메라의 위치는 현재 차량의 진입,진출을 모두 커버 가능해지므로 최대 범위인 진출로 일단 잡아둠.
5. 3,4번 논리를 반복하면서 camera 수와 위치를 수정해주면 해결 되는 문제.

소스 코드

def solution(routes):
    n = len(routes) #자동차 갯수
    answer = 1
    routes.sort(key=lambda x:x[1]) #진출 시점 기준으로 정렬
    camera = routes[0][1]	#카메라 초기 값은 맨 첫 차량의 진출 시점 
    
    for i in range(1,n):
        s,e = routes[i]
        if camera<s:
            camera=e
            answer+=1
        else:
            continue
    
    return answer

print(solution([[-20,-15], [-14,-5], [-18,-13], [-5,-3]]))