[Greed/Sort] BOJ 1931 회의실 배정

문제

1931번: 회의실 배정

 

풀이

1. 회의실 배정이 끝나는 시간을 오름차순 정렬한다. 끝나는 시간이 같다면 시작하는 시간을 오름차순 정렬한다.

2. 정렬된 상태에서 가장 먼저 시작하는 회의를 선택한다.

3. 문제의 조건에 맞춰 선택된 회의의 끝나는 시간보다 같거나 큰 시간의 시작 시간을 가진 회의를 선택한다.

4. 3번을 계속 반복하며 회의를 선택한다.

 

위 과정을 통해 예제 입력1을 풀이한 결과는 다음과 같다.

 

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

 

(8,11),(8,12) 같은 경우 2번을 통해 (8,11) 선택해야한다.

 

코드

import sys

time_list = []

N = int(sys.stdin.readline())

for _ in range(N):
    a,b = map(int,sys.stdin.readline().split())
    time_list.append([a,b])

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

pre_end = time_list[0][1]
cnt = 1

for i in range(1,len(time_list)):
    if time_list[i][0] >= pre_end:
        pre_end = time_list[i][1]
        cnt += 1

print(cnt)