GPU 작업 스케줄러

문제

사내 추론 서버에는 GPU가 한 장뿐이라 작업을 한 번에 하나씩만 처리합니다. i번 작업은 jobs[i] = [요청 시각, 처리 시간] 형태로 주어집니다.

스케줄러는 다음 규칙으로 동작합니다.

• 시각 0에 GPU는 비어 있습니다.
• GPU가 비는 순간, 이미 요청된(요청 시각 ≤ 현재 시각) 작업 중 하나를 골라 즉시 시작합니다.
  • 우선순위: 처리 시간이 짧은 작업 → 같으면 요청 시각이 빠른 작업 → 그것도 같으면 번호(인덱스)가 작은 작업
• 한 번 시작한 작업은 중간에 끊지 않습니다 (비선점).
• 대기 중인 작업이 하나도 없으면 다음 요청이 도착할 때까지 유휴 상태로 기다립니다.

어떤 작업의 대기 시간 은 처리 시작 시각 - 요청 시각입니다. 모든 작업의 대기 시간 중 최댓값 을 반환하는 solution(jobs) 함수를 작성하세요.

예시

jobs=[[0,3],[1,9],[2,6]] → 8
  0번: 시각 0 시작(대기 0), 시각 3 종료
  대기 중 [1번(처리 9), 2번(처리 6)] → 처리 시간 짧은 2번: 시각 3 시작(대기 1), 시각 9 종료
  1번: 시각 9 시작(대기 8) → 최대 대기 8
 
jobs=[[0,10],[2,5],[3,5]] → 12
  0번: 시각 0 시작, 시각 10 종료
  1번·2번 처리 시간이 같으므로 요청이 빠른 1번: 시각 10 시작(대기 8), 시각 15 종료
  2번: 시각 15 시작(대기 12) → 최대 대기 12
 
jobs=[[0,2],[10,3],[11,1]] → 2
  0번 종료(시각 2) 후 시각 10까지 유휴.
  1번: 시각 10 시작(대기 0), 시각 13 종료 / 2번: 시각 13 시작(대기 2)

제약 조건

• 1 ≤ jobs.length ≤ 100,000
• 0 ≤ 요청 시각 ≤ 1,000,000
• 1 ≤ 처리 시간 ≤ 1,000
• 반환값은 정수입니다.

시간 복잡도 목표: O(N log N)

참고: TypeScript에는 내장 PriorityQueue가 없습니다. 직접 힙을 구현해야 대형 케이스를 제한 시간 안에 통과할 수 있습니다.