[Algorithm] 회의실 배정 (Meeting room)

0. 문제

link: https://www.codetree.ai/missions/6/concepts/35/problems/scheduling-meeting-room/introduction

코드트리

하나의 회의실이 있고, n개의 회의 요청이 들어왔다. 각 회의의 시작 시간과 끝 시간이 주어져 있으며, 한 회의가 시작되면 도중에 그만둘 수 없고, 한 회의가 끝나는 직후에 동시에 다른 회의가 시작될 수 있다. 적절하게 회의 요청을 수락하여 최대로 많은 회의가 진행되도록 만들어보자. 

 

이 문제는 회의 끝 시간을 기준으로 정렬하여 가장 빨리 끝나는 회의 중 겹치지 않는 회의를 선택하는 그리디 알고리즘으로 접근한다. 회의 끝 시간을 기준으로 정렬하면, 끝나는 시간이 k인 가장 앞선 회의보다 이후 k'시간 에 끝나는 회의를 선택했을 때, 앞으로 회의에 추가적으로 사용할 수 있는 시간이 항상 더 짧아지기 때문이다. 따라서 항상 일찍 끝나는 회의를 그리디하게 선택하는 것이 최적의 답이다. 

 

2. 구현

 

n = int(input())
time = [[0, 0] for _ in range(n)]

for i in range(n):
    tmp = input().split()
    start, end = int(tmp[0]), (int)(tmp[1])
    time[i][0] = start
    time[i][1] = end

time.sort(key=lambda x:x[1])

res = [time[0]]
idx = 0

for i in range(n):
    if res[idx][1] <= time[i][0]:
        res.append(time[i])
        idx += 1

print(len(res))