그리디. 단속카메라

문제

차들이 지나가는 구간 routes[][]가 주어진다. 최소한의 단속카메라를 설치하시오.
단, 진입구간,진출구간에 카메라가 있어도된다.

해결방향성

정렬이 필요하다. 어쨋든 나가는 지점보다 들어오는 지점이 크면, 단속카메라 개수를 늘리면된다.
처음에 들어오는 지점에따라 오름차순 정렬을 시키고, 들어오는 지점이 같으면 나가는 지점 오름차순 정렬을 시켰는데, 그렇게 되면 들어오는 지점은 작은데 나가는 지점은 큰 경우를 처리할수없다.
따라서, 그냥 나가는 시점을 기준으로 내림차순 정렬 시켜주었다. 그리고 갱신될때마다 우선순위큐에 담아주어 크기를 리턴하였다. (사실 그냥 배열 순회로 해도된다.)

코드

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;
class Solution {
   public int solution(int[][] routes) {
        // 차량의 수
        int len = routes.length;

        Arrays.sort(routes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                /*if (o1[0] == o2[0]) {
                    return o1[1] - o2[1]; // 진출 시점 기준으로 오름차순 정렬
                }*/
                return o1[1] - o2[1]; // 진입시점 기준으로 오름차순 정렬
            }
        });

        // 최대힙 정렬
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
        priorityQueue.add(routes[0][1]); // 처음 진출 지점

        for (int i = 0; i < len; i++) {
            // 진출지점보다 진입지점이 크면
            if (routes[i][0] > priorityQueue.peek()) { // priorityQueue.peek보다 진입지점이 크면
                priorityQueue.add(routes[i][1]); // 해당 진출지점을 넣는다. 최대힙 정렬
            }
        }

        return priorityQueue.size();
    }
}

결론

회의실 배정 비슷했던 문제.