[백준 문제풀기 with Python] #1931번 - 회의실 배정

 

이 문제는 그리디 알고리즘을 이용하여 푸는 문제이다. 

그리디 알고리즘 👇

[알고리즘] 그리디 알고리즘이란?(Greedy Algorithms)

 

그리디 알고리즘이란 선택의 순간마다 당장 눈앞에 보이는 최적인 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 

 

회의실이 가장 많이 이용되려면 현재 사용하고 있는 회의의 종료시간이 빨라야한다.

그리고 한가지 더 고려해야 할 점은 만약 종료시간이 같은 경우이다. 

예를 들어 [시작 시간, 끝나는시간] 이 [2,2] [1,2]가 있는 경우 [1,2]인 회의를 먼저 한 후에 [2,2]인 회의를 선택할 경우 배정할 수 있는 회의가 2개이지만, [2,2]의 회의를 먼저 할 경우 [1,2]는 회의실을 사용하지 못하기 때문에 배정할 수 있는 회의가 1개뿐이다. 

 

따라서 먼저 시작시간으로 정렬 한 후, 종료시간으로 정렬을 해준 뒤 회의실을 배정해준다. 

 

2차원 요소를 기준으로 정렬하는 코드
sorted(list, key = lambda a : a[n])

 

import sys

N = int(sys.stdin.readline())
time = []


for i in range(N):
    start, end = map(int, input().split())
    time.append([start, end])


conference = sorted(conference, key = lambda a : a[0]) # start 기준으로 오름차순 정렬
conference = sorted(conference, key = lambda a : a[1]) # end 기준으로 오름차순 정렬

last_end = 0
cnt = 0

for start, end in conference:
    if start >= last_end:
        cnt += 1
        last_end = end

print(cnt)