[백준 온라인 저지] 회의실 배정

문제 출처

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

1931번: 회의실 배정

 

문제 요구사항

• 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

• https://github.com/Limseunghyun95/Algorithm_study/blob/master/baekjoon/p_1931.py