[BOJ/백준] 1931 - 회의실 배정 (Python)

문제

문제링크

회의들의 시작시간과 끝나는 시간이 주어진다. 

회의가 겹치지 않게 회의실을 사용할 수 있는 회의의 최대 개수를 구하라.

 

풀이

그리디 알고리즘을 사용하기 위해 회의들을 정렬해야 한다.

이 때 정렬기준은 끝나는 시간이다. 끝나는 시간이 같을 경우 회의 시간이 짧아야 하므로 두번째 기준은 시작시간이 된다.

정렬된 회의들의 시작시간과 이전 회의의 끝나는 시간을 비교해 회의실이 사용 가능한 경우에만 1을 더한다.

 

코드

import sys
input=sys.stdin.readline

n=int(input())
meet=[tuple(map(int, input().split())) for _ in range(n)]
meet.sort(key=lambda x: (x[1],x[0]))

time=0
count=0
for start, end in meet:
    if start>=time:
        count+=1
        time=end
print(count)