백준_20126_교수님의 기말고사

교수님의 기말고사

문제

안형찬 교수님은 알고리즘 분석 기말고사를 준비하려고 한다.

알고리즘 기말고사는 총 M분 동안 쉬는 시간 없이 볼 예정이며, 인원이 너무 많아서 공학관 C040호에서 말고 다른 강의실에서 시험을 치를 수 없게 되었다.

공학관 C040호는 0분부터 S분까지 사용 가능하다. S는 무조건 M 이상이기 때문에 안 교수님은 별문제 없이 시험을 치를 것으로 생각하였다. 그러나 공학과 C040호에는 다른 시험도 예정되어 있어서 겹치지 않는 시간을 잡아야 한다.

각 시험은 xi분에 시작해서 yi분 동안 진행하며 서로 겹치지 않는다. 한 시험이 끝난 직후 다음 시험이 있는 경우도 겹치지 않는 것으로 판단한다. 즉, xi + yi ≤ xj 일 때 i 시험과 j 시험은 서로 겹치지 않는다.

안형찬 교수님이 시험을 언제 치를 수 있는지 구해보자.

입력

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

N M S
x1 y1
. . .
xN yN

출력

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

제한

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

예제 입력 1

2 3 5
0 1
4 1

예제 출력 1

1

풀이 및 해설

출력값: 안형찬 교수님이 시험을 시작할 수 있는 시각 출력(시험 치를 수 없으면 -1 출력)

• 기말고사 총 M분 동안 진행, C040호는 S(M<=S)분만 사용 가능(다른 시험과 겹치지 않아야함)

→ 강의실에 예약된 시험 시간 사이에 빈 시간 확인해서 M분동안 시험 치를 수 있는지 확인

1. 예약된 시험 시작 시간 저장할 배열과 종료 시간 저장 배열 생성
2. 종료 시간 저장 배열에 C040 빌릴 수 있는 시작 시간인 0분 미리 넣기
3. 시작 시간 배열에 C040 빌릴 수 있는 종료 시간 S분 마지막에 넣기
4. 시작과 종료 시간 배열 각각 오름차순 정렬(입력값에 정렬되어 들어간다는 말 X)
5. 시험들 간 빈 시간이 M보다 크거나 같은지 확인
   • 크거나 같으면 이전 시험의 종료시간 반환 후 종료
   • 아니면 다음 빈 시간 확인

Code

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

// N: C040호에 예정된 시험 개수, M: 안형찬 교수님의 기말고사 시험 진행 시간, S: C040호 사용 가능한 시간
const [N, M, S] = input[0].split(' ').map(Number);

const startTime = [];
const endTime = [0]; // C040 첫 사용 가능한 시간(0분) 저장
for (let i = 1; i <= N; i++) {
  const [x, y] = input[i].split(' ').map(Number); // x: 시작시간, y: 소요시간
  startTime.push(x);
  endTime.push(x + y); // 한 시험이 끝난 종료 시간 저장
}
startTime.push(S); // C040 마지막 사용 가능한 시간(S분) 저장

startTime.sort((a, b) => a - b);
endTime.sort((a, b) => a - b);

for (let n = 0; n < startTime.length; n++) {
  // 예약된 시험들 간 빈 시간 확인
  if (startTime[n] - endTime[n] >= M) return console.log(endTime[n]);
}
console.log(-1);