프로그래머스 ) 단속카메라

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

코딩테스트 연습 - 단속카메라

 

 

---

정렬 후, 내가 Cover 할수있는 범위를 좁혀가면서 그 범위를 넘었을 시에 필요한 카메라를 증가시켜주는 

 

그리디문제이다.

 

사실 우리 머리는 그리디문제를 잘 못풀게 되어있다.

---

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

class Solution {
    public int solution(int[][] routes) {
          int answer = 1;
	        ArrayList<int[]> al = new ArrayList<>();
	        int size = routes.length;

	        for(int i = 0 ; i < size ; i++) al.add(routes[i]);
	        Collections.sort(al, new Comparator<int[]>() {
	        	@Override
	        	public int compare(int[] o1, int[] o2) {
	        		 return o1[0]-o2[0];
	        	}
			});
	        int CoverMax =  al.get(0)[1];
	        int CoverMin =  al.get(0)[0];
	      for(int i = 1 ; i < size; i++) {
	        	if(al.get(i)[1] < CoverMax) {
	        		CoverMax = al.get(i)[1];
	        	} else if(al.get(i)[0] > CoverMax) {
	        		CoverMax = al.get(i)[1];
	        		answer++;
	        	}
	        }
	        return answer;
    }
}

---