[JAVA] 프로그래머스 단속카메라_최소힙

 

문제 :

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

 

 

접근 : 

 

 - 끝을 기준으로 최소힙에 넣는다.

 

 - 한개 씩 차례대로 빼면서 다음의 시작 지점이 이전의 끝지점보다 큰 경우 끝지점을 갱신하고 정답에 1을 추가한다.

 

 - 끝까지 진행 후 결과값을 출력한다.

 

 

 

코드 구현 :  

 

import java.util.Collections;
import java.util.PriorityQueue;

class Solution {
    private static class Car implements Comparable<Car>{
        int route_in;
        int route_out;
        public Car(int route_in, int route_out){
            this.route_in = route_in;
            this.route_out = route_out;
        }

        public int getRouteIn() {
            return this.route_in;
        }

        public int getRouteOut() {
            return this.route_out;
        }

        @Override
        public int compareTo(Car o) {
            return  o.getRouteOut() - this.getRouteOut();
        }
    }

    public int solution(int[][] routes) {
            PriorityQueue<Car> pq = new PriorityQueue<>(Collections.reverseOrder());

            for(int i = 0 ; i < routes.length ; i++) pq.add(new Car(routes[i][0], routes[i][1]));

            Car now;
            int ans = 0;
            int before = - 30_001;

            while(pq.size() > 0){
                now = pq.poll();
                if(before >= now.getRouteIn()) continue;
                before = now.getRouteOut();
                ans++;
            }
            return ans;
    }
}