백준 알고리즘 1931. 회의실 배정

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

1931번: 회의실 배정

 

전체 코드

def solution(meetings: list):
    meetings.sort(key=lambda x: (x[1], x[0]))

    count = 0
    last_end = 0
    for start, end in meetings:
        if last_end <= start:
            last_end = end
            count += 1

    return count


### submit ###
n = int(input())
meetings = []
for _ in range(n):
    start, end = map(int, input().split(' '))
    meetings.append((start, end))

print(solution(meetings))

 

여담

그리드 알고리즘을 써야하는 것을 알고 있고, 반례가 없는 케이스를 찾았다면 구현은 굉장히 단순해진다. 문제는 그리드 알고리즘을 ‘써야’하는지 파악하는 것과 반례가 되는 케이스가 없는지 조사하는게 생각보다 어렵다는 점이다.

가장 ‘많은’ 회의 개수를 구하기 위해 ‘왜’ end를 기준으로 오름차순 정렬을 하고 그리드 알고리즘을 진행하는지 이해해본다.