[백준] 1931번, 회의실 배정 (파이썬)

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다.

각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자.

단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

입력 조건

• 첫째 줄에 회의의 수 N (1 ≤ N ≤ 100,000) 이 주어진다.
• 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 2^31-1 보다 작거나 같은 자연수 또는 0이다.

출력 조건

• 첫째 줄에 게임의 룰에 맞게 선택한 카드가 적힌 숫자를 출력한다.

입력 예시1

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

출력 예시1

4

 

풀이

import sys
input = sys.stdin.readline
N = int(input())
mylist = []
for _ in range(N):
    mylist.append(list(map(int,input().split())))
#리스트 컴프리핸션
# mylist = [list(map(int,input().split())) for _ in range(N)]

mylist.sort(key=lambda x : (x[1],x[0]))
start = 0
result = 0

for schedule in mylist:
    if schedule[0] >= start:
        start = schedule[1]
        result += 1

print(result)

문제해설

빨리 끝나는 순서대로 정렬하는 그리디 문제이다.

빨리 끝나야 더 많은 회의실 이용횟수를 얻을 수 있기 때문이다.

또한, 끝나는 시간이 같다면 시작하는 시간도 정렬되어 있어야 한다.

예를 들어 2가지의 정렬된 input를 보자

 

#A 예시
2
2 2
1 2

 

#B 예시
2
1 2
2 2

A예시처럼 단순히 끝나는 시간으로 정렬한다면 (2,2)만 선택된 채 output은 1로 나온다

하지만, B예시처럼 되어있다면 (1,2),(2,2) 선택이 가능하다. 그래서 output은 2로 나온다.(문제에서 끝나는 시간과 시작시간이 동일할 수 있다고 했기 때문에)

 

예시에 힌트가 있었다.

원리는 단순한데 생각하기가 쉽지 않고 확실하게 이해하기가 쉽지 않다.