백준 / 시간 관리 / 1263번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 시간 관리 / 1263번 (골드 5단계)

문제 사이트: https://www.acmicpc.net/problem/1263

 

문제 설명

---

나의 풀이

# 일의 개수
n = int(input())

# 일 명단
works = [list(map(int, input().split())) for _ in range(n)]

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

start = works[0][1] - works[0][0]

for i in range(1, len(works)):
    next_start, next_end = works[i]
    if next_end < start:
        start = next_end - next_start
    else:
        start -= next_start

if start > -1:
    print(start)
else:
    print(-1)

---

※ 알아야 할 것

그리디 알고리즘을 이용하여 가장 늦게 시작해도 되는 일을 찾아서 늦게 일을 시작할 수 있는 시간을 찾는 방법을 이용했다.

5 20
1 16
8 14
3 5

이 예시에서 start = 15시 기준으로 오지만 다음 일은 16시 이내로 종료하면 되니깐 16 - 1를 해주면 된다.

16이 아닌 1, 14인 경우(8, 14 제외한다 가정) 15시부터 일을 시작할 수 있지만 14시 일 경우 이미 일을 하고 있으므로 start에서 빼줘야한다.