[파이썬/python] 백준 - 1263 시간 관리

문제

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

---

문제 설명

1. N개의 할일이 입력으로 주어진다.
   1. $S_i, T_i$가 입력으로 주어지는데 이는 각각 $T_i $시간이 걸리고, $S_i$시 까지 일을 처리해야 한다는 의미다.
   2. 0시부터 활동을 시작할 수 있고 동시에 두 개 이상의 일은 같은 시간에 처리할 수 없다.
2. 최대한 늦게 일을 시작할 수 있는 시간을 구한다.

 

---

풀이

그리디와 정렬을 이용해서 문제를 풀이했다.

 

먼저 입력으로 주어지는 각 일을 $[T_i, S_i]$ 형태로 저장했다. 여기서 $T_i$는 일을 처리하는 데 걸리는 시간이고, $S_i$는 해당 일을 반드시 끝내야 하는 마감 시간이다.

 

time 리스트에 모든 일을 저장한 뒤 정렬을 진행했다. 마감 시간이 빠른 작업부터 처리하기 위해 마감 시간인 $S_i$를 기준으로 오름차순 정렬하고, 마감 시간이 같은 경우에는 수행 시간이 더 긴 작업이 먼저 오도록 $T_i$를 기준으로 내림차순 정렬했다. 

 

이제 정렬된 작업들을 순서대로 보면서 실제로 일을 수행할 수 있는 시간을 계산해야 한다.

 

먼저 가장 먼저 마감되는 일을 기준으로 시작 시간을 설정한다. time[0]은 가장 먼저 마감되는 작업이므로, 이 작업의 마감 시간 time[0][1]에서 작업 시간 time[0][0]을 빼면 해당 일을 마감 시간에 맞춰 끝내기 위해 시작해야 하는 시간이 된다.

 

따라서 s,e를 아래와 같이 정의했다.

• s : 일을 시작하는 시간
• e : 현재까지 작업이 끝나는 시간

이후 반복문을 통해 나머지 작업들을 하나씩 확인한다.

 

각 작업에 대해 hour는 해당 작업의 수행 시간이고, ne는 해당 작업의 마감 시간이다.

 

현재 스케줄에 이 작업을 그대로 추가하면 마감 시간을 넘기는지 확인하기 위해 r = (e + hour) - ne 를 계산한다.

여기서 e + hour는 이 작업을 바로 이어서 수행했을 때 끝나는 시간이고, ne는 마감 시간이기 때문에 r은 마감 시간을 얼마나 초과하는지를 의미한다.

 

만약 r < 0이라면
마감 시간을 넘기지 않는다는 의미이므로 단순히 작업을 이어서 수행하면 된다. 따라서 현재 종료 시간 e에 hour를 더해주어 다음 작업의 종료 시간을 갱신한다.

 

반대로 r >= 0이라면
현재 스케줄로는 마감 시간을 초과하게 된다. 이 경우 전체 스케줄을 앞으로 당겨야 한다. 초과된 시간 r만큼 시작 시간 s를 줄여주면 모든 작업이 마감 시간 안에 들어오게 된다. 그리고 현재 작업은 마감 시간에 맞춰 끝나도록 e를 ne로 갱신한다.

 

이 과정에서 s가 0보다 작아지게 되면, 이는 모든 일을 마감 시간 안에 처리하는 것이 불가능하다는 의미가 된다. 따라서 이 경우에는 s를 -1로 설정하고 반복문을 종료한다.

 

이렇게 정렬된 작업들을 순서대로 확인하면서 s와 e를 갱신해 나가면, 모든 일을 마감 시간 내에 처리할 수 있는 경우 중에서 가장 늦게 일을 시작할 수 있는 시간을 구할 수 있다.

---

코드

import sys
input = sys.stdin.readline

n = int(input())
time = sorted([list(map(int,input().split())) for _ in range(n)], key = lambda x: (x[1], -x[0]))

s,e = time[0][1]-time[0][0], time[0][1]

for i in range(1,n):
    if s < 0:
        s = -1
        break

    hour, ne = time[i]
    r = (e + hour) - ne

    if r < 0:
        e += hour
    else:
        e = ne
        s -= r
        
        if s < 0:
            s = -1
            break

print(s)

---

시간복잡도

• 1차 반복문을 통해 N회 반복한다.
• 최악의 경우 $N = 1000$이므로 $O(10^3)$의 시간복잡도를 가진다.