들어가며

탐욕법을 풀다가 만난 흥미로운 문제다. 다양한 해결 방법이 있었는데, 효율이 가장 좋게 나오는 방식을 찾다가 흥미로워서 포스팅하려고 한다.

처음엔 정확히 어느 지점에 단속 카메라를 배치하려고 시도했다. 정확히 어느 지점에 두려고 하니 범위로 지정될 수 밖에 없다는 사실을 깨닫고 멘붕했다.
원리를 이해하면 정확히 배치하지 않더라도 카메라가 몇 개가 필요한지 계산할 수 있다는 부분이 흥미로웠다.

해설

• 먼저 구간의 시작 지점을 기준으로 오름차순 정렬을 한다.
  그러면 앞으로 나오는 구간의 시작은 무조건 앞에 있다는 가정이다. 그렇다면 2가지 경우가 남는다.
• 두번째로 끝 지점을 관리한다. 이전 구간이 언제 끝나는지에 따라 그 다음 카메라 여부가 결정된다.

카메라 배치의 경우

• 이전 구간의 끝 지점 다음에 새로운 구간이 시작되는 경우
  • 겹치는 구간이 없다. 새롭게 카메라를 배치한다.
  • 끝 지점을 갱신한다.
• 이전 구간의 끝 지점 전에 새로운 구간이 시작되는 경우
  • 겹치는 구간이 있다. 카메라를 배치할 필요가 없다.
• 이전 구간의 끝 지점 이후에 새로운 구간이 끝나는 경우
  • 끝 지점을 갱신한다.
• 이전 구간의 끝 지점 전에 새로운 구간이 끝나는 경우
  • 겹치는 구간이 있다. 카메라를 배치할 필요가 없다.
  • 이전 구간 속에 속해있다.
  • 끝 지점을 갱신하지 않는다.

문제

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

function solution(routes) {
  routes.sort((a, b) => a[0] - b[0]);
  let result = 1;
  let latestEnd = routes[0][1];
  for (let i = 1; i < routes.length; i++) {
    let [start, end] = routes[i];
    if (latestEnd < start) {
      result++;
      latestEnd = end;
    }
    if (end < latestEnd) {
      latestEnd = end;
    }
  }
  return result;
}