BOJ 1931: 회의실 배정 [Python 3]

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

1931번: 회의실 배정

한 회의실을 사용하기 위해서 제일 많이 회의를 할 수 있는 방법을 찾는다.

 

import sys
input=sys.stdin.readline
n=int(input())
data=[list(map(int,input().split())) for _ in range(n)]
data.sort(key=lambda x:[x[1],x[0]])
start,end=data[0]
cnt=1
for i in range(1,n):
    start1,end1=data[i]
    if end<=start1:
        start,end=start1,end1
        cnt+=1
print(cnt)

해당 코드에서는 Greedy Algorithm을 사용했다.

Greedy Algorithm이란  말 그대로 '이기적으로 항상 최선의 수를 던진다'라고 이해하면 된다.

앞에서부터 제일 타이트하게 회의를 많이 넣어주면 된다.

 

먼저, 빨리 끝나는 시간으로 정렬을 하고, 이후 그 중에서 같은 시간에 끝나면 빨리 시작하는 시간을 기준으로 정렬을 해준다.

왜냐하면 시작하는 시간으로 정렬을 하면, 끝나는 시간이 매우매우 늦어지면 그 중간에 할 수 있는 회의들은 싹 다 하지 못하게 되기 때문이다. 

 

이후 데이터를 돌면서 앞에서부터 다음 회의 시작이 현재 회의 끝 이후이면 cnt에 추가해준다.