[백준 1263번] 시간 관리 (Python)

> 파이썬, 그리디 알고리즘, 정렬

 

 

 

 

 

📖 문제 : 시간 관리 (Python)

 

 

진영이는 캠프 조교를 온 후 효율적으로 시간 관리를 해야 한다는 것을 깨달았다. 진영이는 하루에 해야 할 일이 총 N개가 있고 이 일들을 편하게 1번부터 N번까지 차례대로 번호를 붙였다.

진영이는 시간을 효율적으로 관리하기 위해, 할 일들에 대해 끝내야할 시간과 걸리는 시간을 적은 명단을 만들었다. 즉, 이 명단은 i번째 일은 일을 처리하는데 정확히 Ti 시간이 걸리고 Si 시 내에 이 일을 처리하여야 한다는 것을 담고 있다. 진영이는 0시부터 활동을 시작할 수 있고, 두 개 이상의 일을 같은 시간에 처리할 수 없다.

진영이가 바라는 점은 최대한 늦잠을 자는 것이다. 문제는 이러한 진영이를 도와 일들은 모두 마감시간 내에 처리할 수 있는 범위 내에서 최대한 늦게 일을 시작할 수 있는 시간이 몇 시인지 알아내는 것이다.

 

 

입력

첫째 줄에 일의 수 N이 입력되고 다음 N개의 줄에 대해 i+1번째 줄에는 i번째 일에 대한 Ti와 Si가 입력된다.

 

출력

진영이가 일을 모두 끝마칠 수 있는 가장 늦은 시간을 출력한다. 만약 0시부터 시작하여도 일을 끝마칠 수 없다면 -1을 출력한다.

 

제한

• 1 ≤ N ≤ 1,000
• 1 ≤ Ti ≤ 1,000
• 1 ≤ Si ≤ 1,000,000

 

 

예제 입력 1 

4
3 5
8 14
5 20
1 16

 

예제 출력 1 

2

 

 

 

 

 

내 코드

import sys

input = sys.stdin.readline

N = int(input())
work = []

for _ in range(N):
    t, s = map(int, input().split())
    work.append((t, s))

work.sort(key=lambda x: (x[1], x[0]), reverse=True)

time = work[0][1]
for i in range(1, N):
    if time < work[i][1]:
        time -= work[i][0]
    else:
        time = work[i][1] - work[i][0]

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

 

 

 

 

 

 

Point ! ⭐️ 

•  

글씨가 좀 안이쁘긴 한데 .. ㅎㅎ 죄송함다

마감시간을 역순으로 정렬하여 뒤에서 부터 작업을 해나가면 됩니다. 

 

여기서 조건을 줘야할 것은

1) 뒤에 해야할 작업의 마감시간이 바로 전 작업 시간과 겹쳤을 경우
2) 제시간에 작업을 수행하지 못할 경우 (모든 작업을 끝낸 시간이 0보다 작을 경우)

입니다. !

완전 그리디 알고리즘이네요

 

 

 

 

 

 

백준

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

1263번: 시간 관리