[JAVA] 탐욕법(Greedy) "단속카메라"

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

각각의 자동차 진입 시간~
	-18	~	-13
		-14	~	~	~	-5
						-5	~	-3
-20	~	~	~	~	~	~	~	~	15

1. 차량이 나간 시점을 기준으로 오름차순으로 정렬한다. 

   -위의 표는 정렬한 순서이다.

2. 차량이 들어온 시점이 기존 카메라 위치보다 우측에 있으면 해당 차량이 나가는 지점에 카메라를 설치한다.

   -파랑색 표시 지점이 알고리즘에 따라 카메라를 설치한 지점이다.

 

import java.util.Arrays;

class Solution {
    public int solution(int[][] routes) {
        int answer = 0;
        int camera = -30001;

        Arrays.sort(routes, (a,b)->Integer.compare(a[1],b[1]));
        for(int[] route : routes){
            if(camera<route[0]){
                camera=route[1];
                answer++;
            }
        }

        return answer;
    }
}

 

카메라를 -30001로 잡은 이유는 차량 진입/진출 지점의 범위가 -30000~30000이기 때문이다.