문제 설명
고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.
고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.
제한사항
이 문제는 최소의 단속 카메라 수로 모든 차량의 경로에 위치할 수 있오록 하는 그리디 문제입니다.
그리디(Greedy): 현재 상황에서 가장 좋아보이는 것만을 선택하는 알고리즘
겹치는 경로를 계속 업데이트 하며 겹치는 경로가 없을 경우에 카메라 수를 추가하는 방법으로 풀었습니다.
def solution(routes):
routes.sort()
c_route = routes[0]
camera = 1
for i in range(1, len(routes)):
if routes[i][1] <= c_route[1]:
c_route[1] = routes[i][1]
if routes[i][0] <= c_route[1]:
c_route[0] = routes[i][0]
else:
c_route = routes[i]
camera += 1
return camera
위 코드의 시간 복잡도는 O(nlogn)입니다.