[lv3] 단속카메라

문제링크

풀이요약

그리디

풀이상세

1. 임의의 $A$ 차량이 단속카메라에 걸리게 하려면, 전입 보다는 전출에 가까이 카메라를 배치하는 것이 다음 차량 역시 포함하여 찍을 확률이 높을 것이다.

2. 따라서, 전출을 기점으로 차량을 정렬한 후, 이전 차량의 전출 값을 저장하여 만약 다음 차량의 전입이 이전의 차량의 전출보다 더 큰 경우에만 다음 차량의 전출 시점에 카메라를 추가하여 배치하는 방식으로 탐색을 진행한다.

import java.util.*;
class Solution {
    public int solution(int[][] routes) {
        int answer = 1;
        Arrays.sort(routes,(n1, n2)-> n1[1]-n2[1]);
        int curr =routes[0][1];
        for(int i=1; i<routes.length; i++) {
            if(curr < routes[i][0]) {
                answer++;
                curr = routes[i][1];
            }

        }
        return answer;
    }
}