[백준] 6068번: 시간 관리하기

문제

백준 - 6068번: 시간 관리하기

분석

N개의 해야할 일에 대한 걸리는 시간과 끝내야하는 시간에 대한 정보가 주어졌을 때, 제 시간에 끝낼 수 있게 결정할 수 있는 한도에서 존이 가장 늦게 시작해도 되는 시간을 구하는 문제이다.

가장 늦게 끝게 끝나는 시간부터 일을 최소 언제부터 시작해야 되는지 판단하면서 진행하다가 시작해야 되는 시간이 0 미만이 되면 불가능하다고 판단했다.
가장 최근에 계산한 일을 시작한 시간(last)보다 끝내야 되는 시간(s)이 더 크면 일하는 데 걸린 시간만큼 last에서 빼준다.
만약 끝내야 되는 시간(s)이 더 작다면 s가 기준이 돼서 걸린 시간만큼 s에서 빼준다.

N까지 도는 for문이 가장 크기 때문에 O(N)이 시간 복잡도이다.

코드

해결언어 : Java

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static PriorityQueue<int[]> pq;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		pq = new PriorityQueue<>((o1, o2) -> o2[1] - o1[1]);
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int t = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			pq.add(new int[] { t, s });
		}
		int last = Integer.MAX_VALUE;
		boolean impossible = false;
		while (!pq.isEmpty()) {
			int[] val = pq.poll();
			int t = val[0], s = val[1];
			if (s >= last) {
				last -= t;
			} else {
				last = s - t;
			}
			if (last < 0) {
				impossible = true;
				break;
			}
		}
		System.out.println(impossible ? -1 : last);
		br.close();
	}

}