SWEA 26793. 게으름뱅이

일 단위의 작업 시간과 마감일이 주어지는 과제들을 최소한 몇일부터 시작해야 하는지 계산하는 문제이다.

 

마지막에 수행해야 할 과제부터 min(현재 시간, 마감일) - 작업 일 계산을 통해 과제들을 최대한 늦게 작업할 수 있게 된다. 이를 위해 과제들을 마감일 기준으로 내림차순 우선순위 큐로 정렬한 후, 모든 작업들을 최대한 늦게 수행할 일을 구한다.

PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
    @Override
    public int compare(int[] o1, int[] o2) {
        return o2[1] - o1[1];
    }
});
            
StringTokenizer st;
            
for(int i=0; i<n; i++) {
    st = new StringTokenizer(br.readLine());
    int d = Integer.parseInt(st.nextToken()), t = Integer.parseInt(st.nextToken());
    pq.add(new int[] {d, t});
}
int time = pq.peek()[1];
            
while(!pq.isEmpty()) {
    int[] current = pq.remove();
    time = Math.min(current[1], time);
    time -= current[0];
}
sb.append(time).append('\n');

 

 

결과 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        
        StringBuilder sb = new StringBuilder();
        for(int tc=1; tc<=T; tc++) {
            int n = Integer.parseInt(br.readLine());
            PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o2[1] - o1[1];
                }
            });
            
            StringTokenizer st;
            
            for(int i=0; i<n; i++) {
                st = new StringTokenizer(br.readLine());
                int d = Integer.parseInt(st.nextToken()), t = Integer.parseInt(st.nextToken());
                pq.add(new int[] {d, t});
            }
            int time = pq.peek()[1];
            
            while(!pq.isEmpty()) {
                int[] current = pq.remove();
                time = Math.min(current[1], time);
                time -= current[0];
            }
            sb.append(time).append('\n');
        }
        
        br.close();
        System.out.print(sb);
    }
}