[JAVA/코딩테스트] 최대 수입 스케쥴(PriorityQueue 응용문제)

설명

현수는 유명한 강연자이다. N개이 기업에서 강연 요청을 해왔다. 각 기업은 D일 안에 와서 강연을 해 주면 M만큼의 강연료를 주기로 했다.

각 기업이 요청한 D와 M를 바탕으로 가장 많을 돈을 벌 수 있도록 강연 스케쥴을 짜야 한다.

단 강연의 특성상 현수는 하루에 하나의 기업에서만 강연을 할 수 있다.

입력

첫 번째 줄에 자연수 N(1<=N<=10,000)이 주어지고, 다음 N개의 줄에 M(1<=M<=10,000)과 D(1<=D<=10,000)가 차례로 주어진다.

출력

첫 번째 줄에 최대로 벌 수 있는 수입을 출력한다.

예시 입력 1 

6
50 2
20 1
40 2
60 3
30 3
30 1

예시 출력 1

150

 

 

import java.util.*;

class Time implements Comparable<Time>{

    public int money;
    public int day;

    Time(int money, int day){
        this.money = money;
        this.day = day;
    }

    @Override
    public int compareTo(Time o){
        if(this.day == o.day){
            return o.money - this.money;
        }else{
            return o.day - this.day;
        }
    }

}


public class Main {

    public int solution(ArrayList<Time> time, int max) {

        int result = 0;

        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());

        int i=0;

        for(int j=max; j>=1; j--){
            for( ; i<time.size(); i++){
                if(time.get(i).day<j){
                    break;
                }else{
                    pq.offer(time.get(i).money);
                }
            }
            // 없으면 런타임 에러
            if(!pq.isEmpty()){
                result += pq.poll();
            }
        }

        return result;
    }

    public static void main(String[] args) {

        Main main = new Main();
        Scanner kb = new Scanner(System.in);

        int n = kb.nextInt();
        int max = 0;

        ArrayList<Time> time = new ArrayList<>();

        for(int i=0; i<n; i++){
            Time tmp = new Time(kb.nextInt(), kb.nextInt());
            time.add(tmp);
            if(max<tmp.day){
                max = tmp.day;
            }
        }

        Collections.sort(time);

        System.out.println(main.solution(time, max));
    }

}