Algorithm/문제
[백준 온라인 저지] 회의실 배정
Lim Seung Hyun
2022. 2. 10. 16:17
문제 출처
1931번: 회의실 배정
(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.
www.acmicpc.net
문제 요구사항
- N개의 회의에 대하여 회의가 겹치지 않게 사용할 수 있는 회의의 최대 개수 구하기
문제 아이디어
- 회의의 시작 시간이 빠른 순으로 정렬하여 문제를 해결하려면 아래와 같은 반례가 존재한다.
- [0, 24], [1, 12], [12, 24]
- 시작시간이 빠른 순으로 정렬해서 풀이를 한다면 [0, 24]만 선택하지만 [1, 12] [12, 24]을 선택하는 것이 최댓값이다.
- 회의의 진행 시간을 기준으로 정렬하여 문제를 해결하려면 아래와 같은 반례가 존재한다.
- [2. 5] [1, 12], [12, 24]
- 진행시간을 기준으로 정렬해서 풀이를 진행하면 [2. 5]만 선택하지만 [1, 12] [12, 24]을 선택하는 것이 최댓값이다.
- 회의의 종료 시간이 빠른 기준으로 정렬하여 문제를 해결해보는 방식으로 진행
- [0, 4] [0, 6] [6, 8] [4, 8] [4, 10] [10, 12] [12, 24]
- 여기서 하나의 선택 사항이 있는데 [6, 8] [4, 8] 은 끝나는 시간이 동일하지만 시작하는 시간이 다르다.
- 이전에서 [0, 4] 회의를 선택하고 이후의 [4, 8] [6, 8] 중에 선택을 하게 되는데 어느 것을 선택해도 끝나는 시간은 동일하고 최적의 해에도 영향이 미치지 않아 선택을 아무거나 해주어도 영향이 없다.
- 필자는 이후에 회의의 최대 개수를 구하면서 가능한 많은 회의 시간을 길게 갖게 만드는 최적의 해를 구하는 문제로도 응용이 가능할 수 있어 시작시간이 빠른 것부터 선택하도록 하였다.
- 전체 시간에서 종료 시간이 빠른 것을 선택하고 뺀 남은 회의 가능한 시간이 어느 회의를 선택하는 것보다 가장 길기 때문에 최적해를 보장할 수 있다.
문제 풀이 (Python3)
import sys
N = int(sys.stdin.readline().strip())
meets = []
for _ in range(N):
s_t, e_t = map(int, sys.stdin.readline().strip().split())
meets.append([s_t, e_t])
sorted_meets = sorted(meets, key = lambda x : (x[1], x[0]))
start_time = 0
answer = 0
for m in sorted_meets:
if start_time == 0 or m[0] >= start_time:
answer += 1
start_time = m[1]
print(answer)- 종료 시간을 기준으로 정렬한 이후 그중에서 가장 빠르게 시작하는 걸 선택하기로 했으므로 sorted에서 key 값을 회의가 종료되는 시간과 시작되는 시간을 순서대로 주었다.
- 문제에서 종료 시간과 동시에 회의가 시작할 수 있도록 조건을 설정해주었다.
Github
728x90