악곱 == 악성곱슬

그리디 알고리즘

---

해당 문제에서 Greedy를 사용할 수 있는 정당성은 다음과 같다고 판단했다.

• 끝나는 시간에 바로 새로운 회의를 시작할 수 있음 ex): 3-5회의 이후 5-7 회의가 바로 가능
• 회의의 시작 시간과 끝나는 시간이 동일할 수 있음

따라서 회의가 끝나는 시간을 기준으로 정렬을 한다면 그리디 알고리즘을 사용하여 문제를 해결할 수 있을 것으로 판단.

import sys
N = int(sys.stdin.readline())
li = list()
for i in range(N):
    li.append(list(map(int, sys.stdin.readline().split())))
# 끝나는 시간을 기준으로 정렬 -> Greedy 를 사용할 수 있는 정당성
li.sort(key=lambda x: (x[1], x[0]))
upper_bound = 0  # 이미 배정된 회의실 시간의 상한(회의 끝나는 시간)
answer = 0  # 배정할 수 있는 회의 개수 정답
for i in range(N):
    if li[i][0] >= upper_bound:
        upper_bound = li[i][1]
        answer += 1
print(answer)