문제

https://baby-ohgu.tistory.com/47

진영이에게 할일 리스트가 있다.
거기에는 걸리는 시간, 마감시간이 적혀있다.
진영이는 0시부터 활동을 시작할수 있고, 두 개 이상의 일을 동시에 처리할수는 없다.
진영이는 최대한 늦잠을 자길 원하기 때문에 마감시간내에 최대한 늦게 일을 시작하는 시간을 구한다.

문제설명

문제가 원하는 답은 최대한 늦게 일을 시작하는 시간이다.
그러기 위해선 마감시간이 제일 뒤인것 부터 앞인거 순으로 탐색을 진행하면 된다.
그러면 일을 마칠수 있는지 아닌지도 판단할 수 있다.

// 정렬 전
3 5
8 14
5 20
1 16

// 마감시간 내림차순 정렬 후
5 20
1 16
8 14
3 5

다음을 보면 이해가 될것이다.

• 뒤에서부터 탐색을 시작하면 처음 마감시간은 20이다.
  최대한 일을 늦게 시작하면 15초에 시작해도 된다.

• 현재 15초, 다음 마감시간이 16초, 걸리는 시간이 1초다.
  그래서 15초에서 1초뺀 14초에 일을 시작해도 충분하다.

• 현재 14초, 다음 마감시간 14초, 걸리는 시간이 8초다.
  여기서 현재 시간이 마감시간 이하이므로 일을 할 수 있다.
  14 - 8 = 6이 된다.

• 현재 6초, 다음 마감시간 5초, 걸리는 시간이 3초다.
  마감시간이 5초이므로 현재 시간을 다음 마감시간 - 걸리는 시간으로 바꿔준다.
  그럼 5 - 3 = 2다.

이렇게 결과는 2가 나오게 된다. 근데 만약 중간에 현재시간이 0 이하가 된다면
더이상 마감시간안에 일을 마칠수 없다는 뜻이 되므로 -1을 리턴해주면 된다.

이를 한번 더 정리하면 이렇다.

works를 마감일 기준 내림차순으로 정렬한다.
	이때, works[i][0] = 걸리는 시간, works[i][1] = 마감시간이다.
time을 최대치보다 1 큰 1,000,001로 지정한다.

works를 순환한다:
	만약 (현재시간 > 현재 일의 마감시간) 이라면:
    	현재시간 = 현재 마감시간 - 현재 걸리는시간
    아니라면:
    	현재시간 = 현재시간 - 현재 걸리는시간
        
    만약 (현재시간 < 1) 이라면:
    	결과로 -1을 반환
        
결과로 현재시간을 반환한다.

정답코드

const stdin = require('fs').readFileSync(0, 'utf-8').trim().split('\n');
const input = (() => {
  let line = 0;
  return () => stdin[line++].split(' ').map(v => +v);
})();

const solution = () => {
  const N = +input();
  const works = Array.from({ length: N }, () => input());
  let time = 1000001;
  
  works.sort((a, b) => b[1] - a[1]);
  
  for (let i = 0; i < works.length; i++) {
    if (time > works[i][1]) time = works[i][1] - works[i][0];
    else time -= works[i][0];
    if (time < 1) return -1;
  }
  return time;
};
console.log(solution());