(백준) 시간관리하기_6068 [java]

https://www.acmicpc.net/problem/6068

 

🐢 설명

소요시간과 제한시간이 있는 작업들에 대해서 전부 처리할 수 있는지 알아내는 문제이다. 만약 처리가 가능하다면 가장 늦게 시작하는 시간을, 불가능하다면 -1을 출력하면 된다.

 

마감시간에 가장 근접하게 작업을 시작해야 가장 늦게 일을 시작할 수 있을 것이므로, 작업의 마감시간이 늦은 시간을 기준으로 정렬시키기 위해 우선순위큐를 사용하였다.

 

모든 작업중 가장 늦게 시작하는 작업의 시간을 DEADLINE으로 정한 후 (우선순위큐를) 순차 탐색하는데 해당 작업의 마감시간이

• DEADLINE보다 더 빨리 시작하는 작업의 경우 : DEADLINE을 (해당 작업의 마감시간 - 해당 작업 소요시간)으로 변경한다.
• DEADLINE이 더 크거나 같은 경우 (똑같이 혹은 더 늦게 끝나도 되는 경우) : DEADLINE을 (DEADLINE - 해당 작업 소요 시간)으로 변경한다. 해당 작업을 현재의 최대 마감시간에 붙여서 하게 하는 것이다.

만약 DEADLINE이 음수가 된다면 작업을 수행하지 못하게 된다는 것이므로 탐색을 종료하고 -1을 출력하면 된다.

🐢코드

public class 시간관리하기_6068 {
    static int N;
    static PriorityQueue<job> pq = new PriorityQueue<>(Comparator.comparingInt(j -> -j.deadLine));

    private static class job{
        int needT;
        int deadLine;

        public job(int needT, int deadLine) {
            this.needT = needT;
            this.deadLine = deadLine;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        int DEADLINE;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int needTime = Integer.parseInt(st.nextToken());
            int deadLine = Integer.parseInt(st.nextToken());
            pq.add(new job(needTime, deadLine));
        }
        DEADLINE = pq.peek().deadLine;

        while (!pq.isEmpty() && DEADLINE >= 0) {
            job now = pq.poll();
            if (now.deadLine < DEADLINE) {
                DEADLINE = now.deadLine - now.needT;
            } else {
                DEADLINE -= now.needT;
            }
        }
        if (DEADLINE > 0) System.out.println(DEADLINE);
        else System.out.println(-1);
    }
}

🐢 마무리