최대 수입 스케쥴(우선순위 큐)

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

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

 

입력 

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

 

출력

150

 

우선순위 큐를 이용하는 문제, 아래처럼 int를 내림차순으로 저장하는 큐를 만들고 

강연 날짜를 할수 있는 마지막 날부터 내림차순으로 정렬한 금액, 날짜 쌍의 금액을 넣는다.

마지막 날 부터 하는 이유 - 3일동안 강연할때 3일째에는 3일날에 하는 강연밖에 못함 -> 3일에 할수 있는 강연중 가장 큰 금액을 주는 강연, 2일날에는 3일에 할수있는 강연과 2일에 할수 있는 강연 중 가장 큰 금액을 주는 강연...

처음에 입력받는 날짜중 가장 큰 값을 기억해두고, 그 날짜의 크기만큼 반복문을 수행한다.

반복문의 안에서는 입력받은 돈과 시간 쌍의 크기만큼 내부 반복문을 돌면서 반복문 요소의 시간이 현재 시간보다 작으면

break로 내부 for문을 탈출하고 현재 큐에서 가장 큰 값을 꺼낸다

 

 

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

import java.util.*;

class Lecture implements Comparable<Lecture>{
    int money;
    int time;

    Lecture(int money, int time){
        this.money = money;
        this.time = time;
    }

    @Override
    public int compareTo(Lecture o) {
        if (this.time == o.time){
            return o.money - this.money;
        }
        return o.time - this.time;
    }
}

class Main{
    static  int max = Integer.MIN_VALUE, money = 0;
    public int Solution(ArrayList<Lecture> arr){
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        int j = 0;
        for (int i = max; i >= 1; i--){
            for (; j < arr.size(); j++){
                if (arr.get(j).time < i) break;
                pq.offer(arr.get(j).money);
            }
            if (!pq.isEmpty()) money += pq.poll();
        }
        return money;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        ArrayList<Lecture> arr = new ArrayList<>();
        int n = in.nextInt();
        for (int i = 0; i < n; i++) {
            int m = in.nextInt();
            int t = in.nextInt();
            arr.add(new Lecture(m, t));
            if (t > max) max = t;
        }
        Collections.sort(arr);
        for (Lecture x : arr) System.out.println(x.money + " " + x.time);
        System.out.println(T.Solution(arr));
    }
}