[Python] 백준 1263번 - 시간관리

1. 문제정보

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

1263번: 시간 관리

 

 

2. 해결전략

시간표 문제와 같이 끝나는 시간을 기준으로 정렬한 후 첫 번째 할 일을 기준으로 시작 시간을 구한다면 해결될 줄 알았지만 문제점은 끝나는 시간이 같더라도 수행하는 시간이 다르다면 시작 시간이 달라질 수 있었기 때문에 한번 더 고민이 필요하다.

 

 그리고 시작 시간을 구하는 것 뿐만 아니라 모든 할 일을 끝낼 수 있는지(중첩되는 시간이 없는지)를 확인이 필요하기 때문에 하나의 일이 끝나면 바로 다음 일을 시작하면서 최대한 촘촘하게 체크해야 한다. 사실 0시부터 반복문을 수행하는 것은 좋은 알고리즘이 아니지만 첫 번째 할 일의 종료 시간까지만 확인하면 되고, 최악의 경우를 가정하더라도 시간 제한이 2초이기 때문에 충분하다고 판단했다.

 

 

3. 코드

import sys

input = sys.stdin.readline

n = int(input())
arr = []
for _ in range(n):
    t, s = map(int, input().split())
    arr.append((t, s))

# 종료 기한일을 기준으로 정렬
arr.sort(key= lambda x: x[1])


# 0시에 일어났을 때부터 확인
start = 0
canWork = True

# 첫번째 업무의 기한일까지만 확인하면 됨
while start <= arr[0][1]:   
    temp = start

    # 모든 업무를 처리할 수 있는지 확인
    for t, s in arr:
        if temp + t <= s:
            temp = temp + t
        else:
            canWork = False
            break
    if not canWork:
        break

    # 모든 업무를 처리할 수 있는 경우 시작 시간 증가
    start += 1

if start == 0 and canWork:
    print(-1)
else:
    print(start-1)