[Baekjoon 1931 / python / 실버1] 회의실 배정

# 끝나는시간으로 정렬하지 않으면 일찍 시작하고 아주 늦게 끝나는 회의에 말릴 수 있다

# 시작시간으로 정렬해야 회의목록을 순차적으로 돌면서 진행 가능하다

import sys

input = sys.stdin.readline

N = int(input())  # 회의 개수

talkList = []  # 회의 리스트 (시작시간, 종료시간)

for _ in range(N):

    talkList.append(list(map(int, input().split())))

talkList.sort(key = lambda x: (x[1], x[0]))  # 회의 리스트 정렬 ( 끝나는시간으로 정렬 후 시작시간으로 정렬 )

cnt = 1  # 회의개수 셀 변수

end = talkList[0][1]  # 첫 회의 끝나는시간을 미리 초기화해둔다

for i in range(1, N):  # 회의 갯수 세기 시작

    if end <= talkList[i][0]:  # 회의 시작시간이 이전회의 끝나는시간과 같거나 크면 회의 + 1

        cnt += 1

        end = talkList[i][1]  # 회의시간 갱신

print(cnt)

 

그리디 알고리즘 문제이다. 문제가 엄청나게 어려운 건 아니었는데 은근히 헷갈렸고 특히 정렬 부분을 신경을 못 써서 많이 헤맸다.

 

회의 리스트를 시작시간 오름차순으로 정렬해서 반복문을 돌며 연속될 수 있는 회의의 개수를 세면 된다. 단, 시작시간 기준으로만 정렬하는 것이 아니라 끝나는 시간으로 정렬 후 시작시간으로 정렬해야 한다.

 

끝나는 시간으로 먼저 정렬하는 이유는 예를 들어,

2, 10

2, 3

이렇게 2개의 회의가 있다고 하자. 정렬해두지 않았다면 먼저 나오는 2, 10 회의가 선택되어 매우 많은 회의가 낭비될 것이다. 그래서 끝나는 시간으로 정렬하면,

2, 3

2, 10

이렇게 정렬되어 시작 시간은 같지만 매우 늦게 끝나는 회의에 말려들지 않을 수 있다.

 

이렇게 해둔 후 시작 순서대로 정렬하면, 끝나는 시간 정렬은 유지된 채로 시작시간 기준으로 정렬되어 순서대로 회의 리스트를 탐방하며 정상적으로 회의 개수를 셀 수 있다.