[백준 BOJ / Python] 1263번 시간 관리

문제

N개의 작업이 주어졌을 때, 각 작업의 마감시간(S)과 소요시간(T)을 고려해 모든 작업을 마감시간 내 완료하면서 가장 늦게 일을 시작할 수 있는 시간을 찾는 문제이다.

작업은 동시에 할 수 없으며 일을 시작할 수 있는 시간은 0부터이다.

풀이

• 제일 마지막 마감시간을 기준으로 뒤에서부터 작업을 배치하면서, 가능한 가장 늦은 시작 시간을 계산한다.

• 먼저 마감시간을 기준으로 데이터를 정렬한다.
• 임의로 시작시간을 무한으로 설정한다.
• 가장 마감시간이 늦은 작업부터 차례대로 확인한다.

• 만약 시작시간보다 다음 작업의 마감시간이 작다면, 마감시간으로부터 소요시간을 뺀 값을 다음 시작시간으로 둔다.
• 만약 시작시간보다 다음 작업의 마감시간이 크다면, 시작시간을 기준으로 소요시간을 뺀 값을 다음 시작시간으로 설정한다.
• 최종적으로 시작시간이 0보다 크면 해당값을 출력하고, 작다면 -1을 출력한다.

Python 코드

import sys
input = sys.stdin.readline

n = int(input())
arr=[tuple(map(int,input().split())) for _ in range(n)]
arr.sort(key=lambda x: x[1])
ans = float("inf")
while arr:
    t,s = arr.pop()
    if ans >= s:
        ans = s-t
    else:
        ans -= t

if ans < 0:
    print(-1)
else:
    print(ans)

 

문제출처

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