파이썬 알고리즘-26 (탐색, 그리디) 회의실 배정

26.회의실 배정(그리디)
한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들
려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하
면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중
단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

▣ 입력설명
첫째 줄에 회의의 수 n(1<=n<=100,000)이 주어진다. 둘째 줄부터 n+1 줄까지 각 회의의 정
보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다.

▣ 출력설명
첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.

▣ 입력예제 1
5 1
4
2 3
3 5
4 6
5 7

▣ 출력예제 1
3

예제설명
(2, 3) , (3, 5), (5, 7)이 회의실을 이용할 수 있다

내 코드

여전히 손도 못대고 있다.

풀이

n=int(input())
meeting=[]
for i in range(n):
    a, b=map(int, input().split())
    meeting.append((a, b))
meeting.sort(key=lambda x : (x[1], x[0]))
et=0
cnt=0
for x, y in meeting:
    if x>=et:
        et=y
        cnt+=1
print(cnt)

반성점

• 계속 걸리는 시간을 어떤 식으로 사용해야되나만 생각나고 다른 방법은 생각조차 못했다.

배운 것

• 그리디 알고리즘 적용 방법: 그리디 알고리즘의 기본 정의는 각 단계에서 최적의 값을 찾는 것이다.(최종적으로는 덜 효율적일지라도) 그렇기 때문에 그리디 알고리즘 문제는 보통 정렬을 어떻게 하고 시작하느냐가 중요하다.
• 정렬을 어떻게 할까: 이번 문제의 경우 최대한 많은 회의를 넣어야 하는데, 그럴 경우 끝나는 시간이 가장 빠른 것을 기준으로 정렬해야한다. 시작 시간이 빠른 것을 기준으로 하면 끝나는 시간이 늦은 경우도 선택될 수 있기 때문.
• 정렬 방법: sort()는 오름차순/내림차순만 가능한 줄 알았는데 람다식을 쓰면 다양한 기준으로 정렬이 가능하다.
  ※람다 표현식 in sort(): sort()의 key 인자에 람다 함수를 넘겨주면 정렬을 더 정교하게 실행할 수있다. 문제에서는 리스트의 정렬 순서를 두번째 원소를 기준으로 우선 정렬하고, 값이 같을 경우 첫번째 원소를 기준으로 정렬하도록 만들었다.
  이는 비단 리스트뿐만아니라 문자열도 n번째 문자를 기준으로 정렬하는 것도 가능케 한다.
  더 좋은 설명은 https://velog.io/@aonee/Python-%EC%A0%95%EB%A0%AC-sort-sorted-reverse 이곳을 참조.