[백준/Python] 1931번: 회의실 배정

문제

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

1931번: 회의실 배정

---

문제 요약

N개의 회의 시작시간, 종료시간을 입력 받고, 한 개의 회의실에서 최대로 사용할 수 있는 회의의 최대 개수를 출력한다.

 

+ 회의 한번 시작하면 중간에 중단될 수 없다.

+ 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

+ 회의의 시작시간과 끝나는 시간이 같을 수 있다. (시작하자마자 종료)

---

코드

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

arr = [] # 모든 회의 시간을 입력 받을 배열

cnt = 1 # 회의 개수

for _ in range(N):
    arr.append(list(map(int, input().split())))
    # 시작시간과 끝나는 시간 입력

arr = sorted(arr, key = lambda x: [x[1], x[0]])
# 먼저 끝나는 회의부터 오름차순 정렬 (같다면 늦게 시작하는 회의부터)

end_tm = arr[0][1] # 마지막 회의의 종료시간

for i in range(1, N):
    if end_tm <= arr[i][0]:
    # 회의시간이 이전 회의가 끝나는 시간보다 늦게 시작한다면
        end_tm = arr[i][1]
        cnt += 1

print(cnt)

---

코드 설명

가장 많은 회의를 진행하기 위한 회의실 배정 방법은 가장 먼저 종료하는 회의를 시간표에 넣는 것이다.

 

1. N개 회의의 시작시간, 종료시간을 입력 받고 정렬한다.

+ 먼저 끝나는 회의부터 오름차순으로 정렬한다. (종료시간이 같다면, 늦게 시작하는 회의부터 정렬한다.)

 

2. 회의실에서의 마지막 회의의 종료시간보다 고를 회의가 더 늦게 시작한다면 선택한다.

+ 마지막 회의 종료시간을 갱신하고 회의 개수를 1 증가시킨다.

 

3. 회의 개수를 출력한다.

---

입력 받은 회의 시간들을 정렬한 배열에서 첫 번째 회의 (가장 빨리 끝나는 회의)는  정답에 반드시 포함해야한다.

 

만약 포함하지 않을 때,

 

1. 두 번째 회의시간이 첫 번째 회의시간과 겹치지 않는다면, 그 회의를 넣어서 답을 하나 더 길게 만들 수 있으므로 모순이다.

 

2. 두 번째 회의시간이 첫 번째 회의시간과 겹친다면, 두 번째 회의시간을 빼고 첫 번째 회의를 포함시켜도 여전히 답이 되기 때문이다.