Programmers / Level 3 / 단속카메라 / JS

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

프로그래머스

 

문제분석

이 문제는 전형적인 구간 스케줄링 문제이다.

여러 구간이 주어졌을 때, 모든 구간을 커버하는 최소한의 점을 찾는 것과 같다.

 

직관적인 접근법

1. 차량들의 경로를 구간으로 생각한다.
2. 겹치는 구간들은 하나의 카메라로 처리가 가능하다.
3. 겹치지 않는 구간들은 각각 별도의 카메라가 필요하다.

 

풀이

핵심 아이디어: 진출 기점을 기준으로 정렬한 후, greedy하게 카메라 위치를 선택한다.

function solution(routes) {
  routes.sort((a, b) => a[1] - b[1]);
  let cameraCount = 0;
  let cameraPosition = -30001;

  for (const [from, to] of routes) {
    if (from > cameraPosition) {
      cameraPosition = to;
      cameraCount++;
    }
  }

  return cameraCount;
}

 

왜 진출 기점 기준일까?

• 해당 구간을 반드시 커버해야 한다.
• 진출 지점에 카메라를 두면, 이후 구간들과의 겹침을 최대화한다.