[Algorithm]알고리즘 자바_71 최대 수입 스케쥴 :: PriorityQueue

 

💬 문제 설명

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

각 기업이 요청한 D와 M를 바탕으로 가장 많을 돈을 벌 수 있도록 강연 스케쥴을 짜야 한다.
단 강연의 특성상 현수는 하루에 하나의 기업에서만 강연을 할 수 있다.

 

🔨 입출력 예

입력 

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

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

 

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

150

 

 

​

💻 Solution.java

/* 최대 수입 스케쥴 :: Priority Queue */

import java.util.*;

class Lecture implements Comparable<Lecture>{
	public int money;
	public int time;
	
	Lecture(int money, int time){
		this.money = money;
		this.time = time;
	}
	
	@Override
	public int compareTo(Lecture o) { //object가 더 크면 음수 리턴, this가 더 크면 양수 리턴, 같은 값은 0 리턴
		return o.time - this.time; // Object에서 지금 값 빼면 내림차 순 
	} 
}

public class Main {
	static int max = Integer.MIN_VALUE, n;

	public int solution(ArrayList<Lecture> arr, int n) {
		int answer = 0;
		PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder()); // 제일 큰 값을 우선 순위로 정
		Collections.sort(arr);
		
		int j = 0;
		for(int i = max; i >= 1; i--) {
			for(; j < n; j++) {
				if(arr.get(j).time < i) break;
				pQ.offer(arr.get(j).money);
			}
			
			if(!pQ.isEmpty()) answer += pQ.poll(); // 가장 큰 값을 poll
		}
		
		return answer;
 	}
	
	public static void main(String[] args){
		Main main = new Main();
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		ArrayList<Lecture> arr = new ArrayList<>();
		
		for(int i = 0; i < n; i++) {
			int m = sc.nextInt();
			int d = sc.nextInt();
			arr.add(new Lecture(m, d));
			if(d > max) max = d;
		}
		
		System.out.println(main.solution(arr, n));
		
		sc.close();
		return ;
	}
}