백준 6068 - 시간 관리하기(Java)

www.acmicpc.net/problem/6068

6068번: 시간 관리하기

1. 유형

그리디, 우선순위 큐

 

2. 풀이

- 자료구조 : 우선순위큐

- 구현기능

• 마감시간이 큰 것 부터 내림차순 정렬
• 시작 시간을 갱신

시뮬레이션을 돌리면 아래처럼 진행될 것이다.

 

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

public class Main {
	static class Pair implements Comparable<Pair> {
		int time;
		int end;

		public Pair(int time, int end) {
			this.time = time;
			this.end = end;
		}

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

	}

	static int N;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = Integer.valueOf(st.nextToken());
		PriorityQueue<Pair> pq = new PriorityQueue<>();
		for (int i = 0; i < N; i++) {
			int time, end;
			st = new StringTokenizer(in.readLine());
			time = Integer.valueOf(st.nextToken());
			end = Integer.valueOf(st.nextToken());
			pq.add(new Pair(time, end));
		}
		Pair tmp = pq.poll();
		int start = tmp.end - tmp.time;
		
		while(!pq.isEmpty()) {
			Pair cur = pq.poll();
			if(start < cur.end) {
				start = start - cur.time;
			}else {
				start = cur.end - cur.time;
			}
		}
		if(start < 0 ) {
			System.out.println(-1);
		}else
			System.out.println(start);
	}
}