[BAEKJOON] 1931_회의실 배정_Python

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

1931번: 회의실 배정

문제

 

 

문제 해설

(1) 회의 수와 회의 시간(시작시간, 끝시간)이 주어진다.
(2) 회의가 겹치지 않게 진행시킬 수 있는 최대 개수를 출력하는 문제이다.

 

 

문제 풀이

풀고나니 쉬워 보이지만, 직관적으로 떠올리기 어려운 풀이였다.

(1) 회의시간을 (끝나는 시간, 시작시간)을 기준으로 다중조건 오름차순 정렬을 한다.
(2) 0번째 회의를 기준점으로 잡고 for문 탐색한다.
(3) 다음 회의 시작시간이 기준점의 끝나는 시간보다 크거나 같다면, 이 회의를 다시 기준점으로 잡고 가능한 회의 개수에 +1 해준다.

위 간단한 알고리즘으로 해결되는데, 이 로직이 가능했던 가장 중요한 이유는 정렬 방식이다.
포인트는 끝나는 시간을 첫번째 기준으로 정렬하는 것인데, 이렇게 하면
가장 처음에 시작하고 먼저 끝나는 회의를 기준점으로 잡을 수 있다. 해당 회의를 counting에 포함시키는 것은 어떠한 경우에서도 최선의 결과에 포함된다.
아래 예시를 보자.

회의 (1) 이후에 나올 수 있는 회의의 경우의 수를 나타낸 것으로 총 (2) ~ (5) 4가지가 전부이다. 이 경우에서 최선의 조합을 찾으면, [1, 4]가 된다. [2, 4]도 가능하긴 하지만, 뒤에 다른 회의들이 무수히 많이 있다고 가정할 시, 1을 선택하든 2를 선택하든 최대 개수에 미치는 영향은 없다.
위의 경우 정렬을 통해 항상 최선의 조합을 선택할 수 있게 된 것이다.

 

 

* 코드

from sys import stdin

N = int(stdin.readline())
meetings = []

for i in range(N):
    s, e = map(int, stdin.readline().rstrip().split())
    meetings.append([s, e])

meetings = sorted(meetings, key=lambda x: (x[1], x[0]))
start, end = meetings[0]
answer = 1

for i in range(1, len(meetings)):
    if meetings[i][0] >= end:
        start, end = meetings[i]
        answer += 1

print(answer)