[백준(BOJ)] 1931번 회의실 배정 - 파이썬/python

문제

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

 

회의의 수 N과 회의의 정보가 주어질 때, 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 구하는 문제다.

 

예시

Example :

Input:
11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14
Output:
4

• (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

 

풀이

회의실을 사용할 수 있는 회의의 최대 개수를 구하는 문제이기 때문에 정렬이 필요하다고 생각했다.

정렬은 시작 시간이 아닌 종료 시간을 기준으로 하여 빨리 종료되는 구간을 먼저 선택해 가능한 한 많은 구간을 선택해야 한다.

(그리디 알고리즘)

import sys
input = sys.stdin.readline

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

lst.sort(key=lambda x: (x[1], x[0]))

cnt = 0
now = 0

for start, end in lst:
    if now <= start:
        now = end
        cnt += 1

print(cnt)

• 회의 시작 시간과 종료 시간을 입력 받아 리스트에 튜플 형태로 저장한다.
• 종료 시간을 기준으로 정렬한다. 종료 시간이 동일한 경우 시작 시간을 기준으로 정렬한다.
• 'now'에 현재 선택된 구간의 종료 시간을 저장하고, 회의 시간을 순서대로 확인하면서 시작 시간이 이전에 선택된 구간의 종료 시간보다 크거나 같을 때 해당 구간으로 갱신하고 개수를 증가시킨다.