최대 수입

Priority Queue 사용.

 

 

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

class Main {

	static int m, n, answer;

	public static void main(String args[]) throws Exception {
		Main M = new Main();
		Scanner in = new Scanner(System.in);
		n = in.nextInt();

		ArrayList<Class> ar = new ArrayList<>();
		int max =0;
		for (int i = 0; i < n; ++i) {
			int m = in.nextInt();
			int d = in.nextInt();
			max = Math.max(max, d);
			ar.add(M.new Class(m, d));
		}


		
		Collections.sort(ar,Collections.reverseOrder());
		
		for ( Class c : ar) {
			System.out.println(String.format("%d %d", c.m, c.d));
		}

		PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());
		
		System.out.println("max : "+max);
		int j=0;
		for (int i = max ; i >=1 ; i--) {
			for ( ; j < n ; j++ ) {
				if(ar.get(j).d < i) {
					break;
				}
				pQ.offer(ar.get(j).m);
			}
			if (!pQ.isEmpty()) {
				int m = pQ.poll();
				answer+=m;
			}
			
		}

		System.out.println(answer);

	}

	class Class implements Comparable<Class> {
		int m, d;

		Class(int money, int day) {
			this.m = money;
			this.d = day;
		}

		@Override
		public int compareTo(Main.Class o) {
				return this.d - o.d;
		}

	}

}


ex)
input
6
50 2
20 1
40 2
60 3
30 3
30 1

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

max : 3
150