로봇 작업 스케줄
실버 I의견: 0
공장의 로봇은 \(N\)가지 작업을 순서대로 혼자 처리해야 한다. 작업은 한 번에 하나씩, 중단 없이 처리하며, 로봇은 시각 \(0\)부터 쉬지 않고 작업한다.
\(i\)번 작업의 처리 시간은 \(p_i\)이고 마감 시간은 \(d_i\)이다. 작업 \(i\)의 완료 시각이 \(C_i\)라면, 이 작업의 지연량(lateness)은 \(C_i - d_i\) 이다 (음수일 수 있음).
모든 작업 중 최대 지연량을 최소화하는 처리 순서를 구하고, 그 최솟값을 출력하여라.
최대 지연량이 음수이면 모든 작업이 마감 이전에 끝났다는 뜻이다.
- \(1 \le N \le 100\,000\)
- \(1 \le p_i \le 10^6\)
- \(1 \le d_i \le 10^9\)
첫째 줄에 작업의 수 \(N\)이 주어진다.
다음 \(N\)개의 줄에 \(i\)번 작업의 처리 시간 \(p_i\)와 마감 시간 \(d_i\)가 공백으로 구분되어 주어진다.
최대 지연량의 최솟값을 출력한다.
3
3 5
1 3
4 6
2
마감 시간 오름차순으로 정렬하면 \((1,3),(3,5),(4,6)\) 순이다. 완료 시각은 \(1, 4, 8\)이고 지연은 각각 \(1-3=-2\), \(4-5=-1\), \(8-6=2\)이다. 최대 지연 = \(\max(-2,-1,2) = 2\)가 최솟값이다.
3
2 3
5 4
1 2
4
마감 오름차순으로 정렬하면 \((1,2),(2,3),(5,4)\)이다. 완료 시각은 \(1, 3, 8\)이고 지연은 \(1-2=-1\), \(3-3=0\), \(8-4=4\)이다. 최대 지연 = \(\max(-1,0,4) = 4\)가 최솟값이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
로봇 작업 스케줄
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
로봇 작업 스케줄