문제

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

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

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

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

---

입력

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

---

출력

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

---

풀이

접근방법

시간제한 2초, 메모리 128MB이다.

1 ≤ N ≤ 1,000
1 ≤ Ti ≤ 1,000
1 ≤ Si ≤ 1,000,000

전형적인 그리디 문제이다.

문제를 살펴보면 아래와 같은 조건이 있다.
진영이는 0시부터 활동을 시작할 수 있고, 두 개 이상의 일을 같은 시간에 처리할 수 없다.

즉, 선형 시간 내 해야할 일들을 겹치지 않게 배치하면 된다.

앞에서부터 일을 배치하게 된다면 고려해야할것이 많아진다.
뒤에서부터 하나씩 채워보자.

만약 종료시간이 같다면, 어떻게 해야할까.

// 입력예시
2
2 9
3 9

아래 이미지에서 빨간색으로 표시된 것과 파란색으로 표시된 것을 보자.
3시간이 걸리고 9에 종료되는 일을 먼저 한다고 가정해보자.
2시간이 걸리고 9에 종료되는 첫 번째 일은 남은 시간 중 가장 빠른 6까지 완료하면 된다.

- 종료시간이 가장 늦은 일을 가장 뒤에 배치한다.
	a. 종료시간이 같은 일이 있다면, 아무거나 배치.
- 현재 작업의 종료시간과 이전 작업의 시작시간을 고려하여 다음 일 진행.

만약 일을 진행하고자 하는데 이 일을 끝내기 위해 0시보다 먼저 시작해야 한다면, 만약 0시부터 시작하여도 일을 끝마칠 수 없다면 -1을 출력한다. 조건에 따라 -1을 출력한다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	static class Work implements Comparable<Work> {
		int processTime;
		int end;

		Work(String[] str) {
			processTime = stoi(str[0]);
			end = stoi(str[1]);
		}

		@Override
		public int compareTo(Work o) {
			return o.end - this.end;
		}
	}

	static int N;
	static Work[] works;

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

		N = stoi(in.readLine());
		works = new Work[N];
		for (int i = 0; i < N; ++i)
			works[i] = new Work(in.readLine().split(" "));

		Arrays.sort(works);
		int time = works[0].end; // Si의 최댓값
		for (int i = 0; i < N; ++i) {
			time = Math.min(works[i].end, time) - works[i].processTime;
			if (time < 0) { // 0시에 시작해도 끝낼 수 없는 경우
				time = -1;
				break;
			}
		}
		System.out.println(time);
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}