[알고리즘 연습] 회의실 배정

회의실배정

• https://www.acmicpc.net/problem/1931

---

n = int(input())
meet_list = []

for _ in range(n):
    meet_list.append(list(map(int, input().split())))


meet_list.sort(key=lambda x: [x[1],x[0]])

result = 1
last_book_end_time = meet_list[0][1]

for idx in range(1, len(meet_list)):
    if last_book_end_time <= meet_list[idx][0]:
        result += 1
        last_book_end_time = meet_list[idx][1]

print(result)

• 그리디 알고리즘으로 쉽게 풀 수 있는 문제다. 하지만 단순함을 바로 발견하지 못하면 이리저리 헤맬 수 있다.
• 시간이 겹친다면 '빨리끝나는' 것이 우선이라는 것을 파악하는 것이 포인트이다.
• 시작시간과 종료시간을 리스트로 리스트에 저장(이차원리스트)하고, 종료시간이 빠른 것이 앞에 오도록 우선 정렬 후 종료시간이 겹칠 경우 시작 시간 기준으로도 정렬되도록 했다.
• 이 후엔 첫번째 종료시간을 기준으로 다음에 올 수 있는 회의를 추가해주면서 결과를 도출했다.