[백준 - 1263][GOLD 5][해설 X] - 시간 관리 (JAVA)

문제 링크

---

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

 

문제

---

진영이는 캠프 조교를 온 후 효율적으로 시간 관리를 해야 한다는 것을 깨달았다. 진영이는 하루에 해야 할 일이 총 N개가 있고 이 일들을 편하게 1번부터 N번까지 차례대로 번호를 붙였다.

진영이는 시간을 효율적으로 관리하기 위해, 할 일들에 대해 끝내야할 시간과 걸리는 시간을 적은 명단을 만들었다. 즉, 이 명단은 i번째 일은 일을 처리하는데 정확히 Ti 시간이 걸리고 Si 시 내에 이 일을 처리하여야 한다는 것을 담고 있다. 진영이는 0시부터 활동을 시작할 수 있고, 두 개 이상의 일을 같은 시간에 처리할 수 없다.

진영이가 바라는 점은 최대한 늦잠을 자는 것이다. 문제는 이러한 진영이를 도와 일들은 모두 마감시간 내에 처리할 수 있는 범위 내에서 최대한 늦게 일을 시작할 수 있는 시간이 몇 시인지 알아내는 것이다.

 

입력

---

첫째 줄에 일의 수 N이 입력되고 다음 N개의 줄에 대해 i+1번째 줄에는 i번째 일에 대한 Ti와 Si가 입력된다.

 

출력

---

진영이가 일을 모두 끝마칠 수 있는 가장 늦은 시간을 출력한다. 만약 0시부터 시작하여도 일을 끝마칠 수 없다면 -1을 출력한다.

 

해결 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

/*
	가장 마지막으로 시작하는 시간 = 모든 작업을 가능한 마지막날에 가까운 시간에 제출했을 때의 시간
*/

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
		
        //마감시간이 가장 늦게 끝나는 순으로 정렬
        PriorityQueue<Work> pq = new PriorityQueue<>((a,b)->(b.deadline - a.deadline));

        for(int i=0;i<N;i++){
            StringTokenizer st= new StringTokenizer(br.readLine());

            pq.add(new Work(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())));
        }	
        
		//가장 마지막날의 마감시간을 기준으로 가능한 늦은 시간을 계산
        Work last = pq.poll();
        int time = last.deadline - last.time;
		
        //현재 시간을 이용해 가장 늦은시간 갱신
        while(!pq.isEmpty()){
            Work curr = pq.poll();

            time = Math.min(time,curr.deadline) - curr.time;
        }

		//만약 현재 시간이 음수면 제한된 시간대에 작업을 끝내지 못한다.
        if(time < 0){
            System.out.println(-1);
        }else{
            System.out.println(time);
        }
    }
}
class Work {
    int time;
    int deadline;

    public Work(int time, int deadline) {
        this.time = time;
        this.deadline = deadline;
    }
}

 

 

실행 결과

---

 

팁

---

• 가장 늦게 시작하기 = 가장 늦게 끝내기
• 제한된 시간내에 시계열 단위의 작업을 빠르게/늦게 끝내야 되는 문제는 그리디일 확률이 높다.