진영이는 하루에 해야 할 일이 총 N개가 있고 이 일들을 편하게 1번부터 N번까지 차례대로 번호를 붙였음
명단에서 i번째 일은 일을 처리하는데 정확히Ti 시간이 걸리고 Si 시 내에 이 일을 처리하여야 한다는 것을 담고 있음
진영이는 0시부터 활동을 시작할 수 있고, 두 개 이상의 일을 같은 시간에 처리할 수 없음
진영이가 바라는 점은 최대한 늦잠을 자는 것
일들은 모두 마감시간 내에 처리할 수 있는 범위 내에서 최대한 늦게 일을 시작할 수 있는 시간이 몇 시인지알아내기
입력
첫째 줄에 일의 수 N이 입력되고 다음 N개의 줄에 대해 i+1번째 줄에는 i번째 일에 대한 Ti와 Si가 입력
1 ≤ N ≤ 1,000
1 ≤ Ti ≤ 1,000
1 ≤ Si ≤ 1,000,000
출력
진영이가일을 모두 끝마칠 수 있는 가장 늦은 시간을 출력
만약0시부터 시작하여도 일을 끝마칠 수 없다면 -1을 출력
시간 제한: 2초
메모리 제한: 128 MB
"""
입출력 예시)
4
3 5
8 14
5 20
1 16
-> 2
"""
## 의사코드 ##
# 걸리는 시간(Ti) / 마감 시간(Si)
# 마감 시간이 빠른 순서대로 정렬
# -> li.sort(key=lambda x:x[1])
# 최대한 늦게 일을 시작할 수 있는 시간 = 정렬한 리스트[0]의 마감 시간 - 걸리는 시간
# 0시부터 시작하여도 일을 끝마칠 수 없다면 -1
첫 번째 시도
n = int(input())
li = []
for _ in range(n):
t, s = map(int, input().split())
li.append((t, s))
# 마감 시간이 빠른 순서대로 정렬
li.sort(key=lambda x:x[1])
# 최대한 늦게 일을 시작할 수 있는 시간
ans = li[0][1] - li[0][0] # 마감 시간이 제일 빠른 일의 마감 시간 - 걸리는 시간
# 0시부터 시작해도 일을 끝마칠 수 없다면 -1
print(-1 if ans < 0 else ans)
-> 틀림
통과한 코드
n = int(input())
li = []
for _ in range(n):
t, s = map(int, input().split())
li.append((t, s))
# 마감 시간이 가장 늦는 일부터 내림차순 정렬
li.sort(key=lambda x:x[1], reverse=True)
# 시작 시간
ans = li[0][1] - li[0][0] # 마감 시간이 가장 늦는 일의 시작 시간 (마감 시간 - 걸리는 시간)
for i in range(1, n):
# i번째 일의 마감 시간이 현재 시작 시간보다 앞서는 경우, i번째 일을 시작할 수 있는 가장 늦은 시간으로 시작 시간 갱신
if ans > li[i][1]:
ans = li[i][1] - li[i][0]
# i번째 일의 마감 시간이 현재 시작 시간보다 앞서지 않는 경우, i번째 일을 완료하는데 걸리는 시간만큼 현재 시작 시간에서 빼기
else:
ans -= li[i][0]
# 0시부터 시작해도 일을 끝마칠 수 없다면 -1
print(-1 if ans < 0 else ans)
-> 마감 시간이 가장 늦는 일부터 내림차순 정렬 후, 마감 시간이 가장 늦는 일의 시작 시간부터 거꾸로 계산
과정 확인
"""
원본 리스트: [(3, 5), (8, 14), (5, 20), (1, 16)]
정렬된 리스트: [(5, 20), (1, 16), (8, 14), (3, 5)]
현재 시작 시간(마감 시간이 가장 늦는 일의 시작 시간): 15
현재 시작 시간: 15
i번째 일의 걸리는 시간, 마감 시간: (1, 16)
i번째 일의 마감 시간이 현재 시작 시간보다 앞서지 않는 경우
갱신된 시작 시간: 15 - 1
14
현재 시작 시간: 14
i번째 일의 걸리는 시간, 마감 시간: (8, 14)
i번째 일의 마감 시간이 현재 시작 시간보다 앞서지 않는 경우
갱신된 시작 시간: 14 - 8
6
현재 시작 시간: 6
i번째 일의 걸리는 시간, 마감 시간: (3, 5)
i번째 일의 마감 시간이 현재 시작 시간보다 앞서는 경우
갱신된 시작 시간: 5 - 3
2
"""
