BOJ(백준) 1931번 회의실 배정 파이썬

1931번: 회의실 배정

---

코드

import sys
r=sys.stdin.readline
N=int(r())
l=[[0,0] for _ in range(N)]
res=[]
for i in range(N):
    start,end=map(int,r().split())
    l[i][0] = start
    l[i][1] = end
l.sort(key=lambda x:(x[1],x[0]))
res.append(l[0])
for i in range(1,N):
    if res[-1][1] <= l[i][0]:
        res.append(l[i])
print(len(res))

 

해설

Greedy 알고리즘의 대표적인 활동 선택 문제(Activity Selection Problem) 예제이다. 인풋의 회의 시작시간과 끝나는 시간들을 2차원 배열로 저장 후 끝나는 시간 순으로 정렬하였다. 그 후 끝나는 시간이 동일한 회의들은 다시 시작 시간으로 정렬하였다. 그 후 빈 리스트 res 에 첫 회의 시작 시간, 끝나는 시간을 추가해준 후 포문을 순회하며 res 의 마지막 회의의 끝나는 시간보다 l 의 회의 시작 시간이 같거나 늦은 경우 res 에 추가하였다.

 

결과