[Programmers] 단속카메라

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

---

그리디로 풀었다.

먼저 루트들을 시작위치를 기준으로 오름차순정렬한다.

변수를 만들어서 커버가능한 시작위치 종료위치(let, cover)를 저장한다.

루트들을 처음부터 탐색하면서 탐색 중인 루트(let, route)가 이전 가능한 카메라 위치로 커버가능한지 체크한다.

만약 route.시작위치 > cover.종료위치 이거나 route.종료위치 < cover.시작위치 라면 범위가 커버가 불가능하므로 카메라를 한 대 더 설치해야한다. 카메라 대수를 한 대 증가시키고 cover 변수를 현재 route 범위로 갱신한다.

이전 카메라로 커버가 가능하다면 현재 route 범위와 cover 범위의 교집합으로 cover 변수를 갱신해야 한다.

따라서 큰 값(cover.시작위치, route.시작위치), 작은 값(cover.종료위치, route.종료위치)로 cover 변수를 갱신한다.

 

시간복잡도는 정렬하는데 드는 시간인 O(NlogN). N = |routes|.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/programmers/Greedy/%EB%8B%A8%EC%86%8D%EC%B9%B4%EB%A9%94%EB%9D%BC.cpp