[Python] 회의실 배정 - 백준 (그리디)

해당 글은 백준 1931번 문제 '회의실 배정'을 다룬다.

문제

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

1931번: 회의실 배정

 

설명

정렬을 통해 그리디하게 풀 수 있는 문제이다.

(회의 시작 시간, 회의 끝나는 시간)인 여러개의 회의 시간을 입력받은 것을

1) 회의 끝나는 시간, 2) 회의 시작 시간 순으로 정렬을 해준다.

끝나는 시간과 동시에 다음 회의가 시작될 수 있으므로, 이전의 회의가 끝나는 시간보다 현재 회의의 시작 시간이 크거나 같다면 count를 해준다.

 

코드

n = int(input())
time = []
for i in range(n):
    time.append(list(map(int, input().split())))

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

count = 1
end_time = time[0][1]
for i in range(1, n):
    if time[i][0] >= end_time:
        count += 1
        end_time = time[i][1]
print(count)