[백준] 1931번 - 회의실 배정 (파이썬)

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

1931번: 회의실 배정

 

[코드]

import sys

N = int(sys.stdin.readline())
schedule = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
schedule.sort(key=lambda x: (x[1], x[0]))

end_time = 0
meetings_cnt = 0

for i in range(N):
    if end_time <= schedule[i][0]:
        end_time = schedule[i][1]
        meetings_cnt += 1
        
print(meetings_cnt)

 

[참고]

파이썬 내장함수 sort() 에 키값을 설정하면 원하는 기준으로 정렬할 수 있다.

이때 위 문제와 같이 끝나는 시간으로 오름차순, 그중 같은 것은 시작시간으로 오름차순으로 정렬하고 싶다면,

다시말해 두가지 기준으로 정렬하고 싶다면 다음과 sort() 함수를 두번 호출해도 되나 다음과 같이 할 수 있다.

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

 

[설명]

그리디 알고리즘을 이용하여 끝나는 시간이 빠른 순으로 정렬후 우선적으로 배치하는 것이 최대로 회의를 배정할 수 있다는 것은 직관적으로 이해하기 쉽다.

근데  왜 그 시작시간이 빠른 순으로 정렬해야 하는걸까? 그건 시작시간과 끝나는 시간이 같은 회의가 존재하기 때문이다.

예를들어 [1, 3], [2, 3], [3, 3] 순서대로 정렬되어있으면 [1, 3] 배정후 [3, 3] 회의를 배정할 수 있다. 

하지만 [3, 3], [1, 3], [2, 3] 으로 정렬되어 있으면 [3, 3] 배정후 [1, 3] 회의를 배정할 수 없다.