[그리디/Greedy] 백준 1931 회의실 배정 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1931번: 회의실 배정

 

 

 

2. 문제 풀이

 최대한 많은 회의를 수용하는 문제입니다.

 

2022.01.26 - [Algorithm] - [Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결

[Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결

 브루트포스 알고리즘으로 모든 경우의 수를 고려할 수도 있겠지만, 그 보다 더 쉽게 풀 수 있습니다.

 더 많은 회의를 진행하려면, 짧은 회의를 최대한 빈 곳 없이 진행하면 됩니다. 여기서 중요한 점은 '시작시간'이 아니라 '종료시간'입니다. 시작시간이 빨라도 종료시간이 긴 회의라면, 최적 선택이 아닙니다. (예제에서 0-6을 고르게 됨)

 반대로 우선순위를 종료시간(1순위)과 시작시간(2순위)으로 두면, 빠르게 끝나는 회의부터 진행할 수 있습니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

N = int(input())
room = []
for _ in range(N):
    start, end = map(int, input().split())
    room.append([start, end])

#끝나는 시간이 빠른 순서대로 정렬
room.sort(key=lambda x: (x[1], x[0]))

cnt = 0 #회의 개수
time = 0 #시간
for i in room:
    # 시간이 시작시간 이전일 경우, 회의 시작
    if time <= i[0]:
        cnt += 1
        time = i[1] #회의가 끝나는 시간으로 설정
print(cnt)

  종료 시간이 빠른 순서대로 정렬하고, 같을 경우 시작 시간이 빠른 걸 우선으로 합니다.

 이후, 순차적으로 회의 시간을 조율합니다. 앞선 회의가 끝나는 시간 이후로 시작하는 회의이면 count를 1 올리고, 해당 회의 종료시간으로 시간을 조정합니다.