[Algorithms] 결정&그리디 알고리즘-회의실 배정(그리디 알고리즘)

• 그리디 알고리즘 - 문제를 풀어나가는 과정에 있어서 이 단계에서 가장 좋은게 무엇인지 판단하고 선택
• 보통의 그리디 문제는 정렬 후 차례로 선택해 나가게 된다. 거의 대부분이 정렬과 동반되어 문제풀이를 한다.
• 여기서 중요한 것은 sort(key=) 함수를 잘 알아야 한다!

import sys
 
# sys.stdin = open("input", "rt")
n = int(input())
meeting = [list(map(int, input().split())) for _ in range(n)]
 
#회의가 끝나는 시간에 맞추어 sorting을 진행한다
#key는 sort의 기준을 말하는데 여기서는 끝나는 시간을 먼저 기준으로 sorting을 하고
#그 다음에 시작 시간을 기준으로 보라고 명령하고 있다
meeting.sort(key=lambda x: (x[1],x[0]))
 
cnt=0
end_time=0
for s, e in meeting:
    if s >= end_time:   # 시작 시간이 이전 끝나는 시간보다 크거나 같으면 진행
        cnt+=1
        end_time=e
print(cnt)