1931번 - 회의실 배정(Python)

풀이

그리디 알고리즘을 이용해 문제를 해결한다.

 

회의 정보를 끝나는 시간을 기준으로 오름차순 정렬한다.

가장 빨리 끝나는 회의부터 시작해서, 이후의 회의 중 이전 회의가 끝난 후 진행할 수 있는 회의를 다음 회의로 결정한다.

끝나는 시간이 같다면, 먼저 시작하는 회의부터 진행한다.

(3 3 회의와 2 3 회의가 있다면, 2 3 회의부터 진행해야 3 3 회의까지 진행할 수 있도록 된다.)

코드

N = int(input())

meetings = [list(map(int, input().split())) for _ in range(N)]

meetings.sort(key=lambda x: (x[1], x[0]))
ans = 0
end = -1

for i in range(N):
    if meetings[i][0] >= end:
        end = meetings[i][1]
        ans += 1

print(ans)