백준20126-교수님의 기말고사 풀이, java

백준20126-교수님의 기말고사 풀이, java

 

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

20126번: 교수님의 기말고사

문제

알고리즘 기말고사는 총 M분이 필요하다 

시험장은 1개이며, 이미 다른 시험이 예약되어있다.

다른 시험은 시작시간과 시험시간이 주어진다.

시험을 언제 시작할 수 있는지 구하라.

입력

다음과 같이 입력이 주어진다.

N M S
x1 y1
. . .
xN yN

출력

교수님이 시험을 시작할 수 있는 시각을 출력하여라. 시작 가능한 시각이 여러 개 있으면 그중 가장 앞선 시각을 출력한다. 시험을 치룰 수 없다면 -1을 출력하여라.

제한

• 1 ≤ N ≤ 100,000.
• 1 ≤ M ≤ S ≤ 1,000,000,000. 
• 0 ≤ xi < xi + yi ≤ S.
• 입력에 주어진 수들은 전부 정수다.

 

 

풀이

• 시험시작시간을 기준으로 정렬한다
• For 문 돌면서 M분짜리 시간을 넣을 수 있는지 체크한다.
• 만약 M분짜리 시험칠 수 있으면 break 치고 끝낸다
• 주의점은 예약된 시험과 0시 사이에도 시험을 칠 수 있다는 점이다

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

/**
 * https://www.acmicpc.net/problem/20126
 * title : 교수님의 기말고사
 * @author tempcru
 */
public class Main {

	// N <= 10만
	// M,S <= 10억
	
	static int N,M,S;
    static int[][] exams;
	
	public static void main(String[] args) throws Exception {

//		System.setIn(new FileInputStream("./src/B20126/sample_data"));
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		StringTokenizer st = new StringTokenizer(br.readLine().trim());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());
		
		exams = new int[N][2];
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			exams[i][0] = Integer.parseInt(st.nextToken());
			exams[i][1] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(exams, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) { 
				return o1[0] - o2[0];
			}
		});
		
		System.out.println(search_empty());
		
	}

	private static int search_empty() {
		
		
		int result = -1;
		
		// 0 이전
		int temp = exams[0][0] - M;
		if(temp > -1) {
			return 0;
		}
		
		
		// 0 ~ N-1
		for(int i = 0; i < N-1; i++) { 
			temp = exams[i+1][0] - exams[i][0] - exams[i][1] - M;
			if(temp > -1) {
				result = exams[i][0] + exams[i][1];
				break;
			}
		}
		
		// N-1
		if(result < 0) {
			temp = S - exams[N-1][0] - exams[N-1][1] - M;
			if(temp > -1) {
				result = exams[N-1][0] + exams[N-1][1]; 
			}
		}
		
		return result;
	}

}