[백준] 회의실 배정(1931) - python

✏️ 문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

🎈 입력

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

🎈 출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

🎈 입출력 예

<입력>
11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

<출력>
4

👩‍💻 내 코드

이 문제는 그리디 알고리즘을 이용해 푸는 문제이다. 처음엔 복잡하게 생각하여 조금 난이도 있는 문제라고 생각했는데 파이썬 정렬에 관련해 잘 알고 있다면 쉽게 풀 수 있다는 것을 알 수 있었다. 이 문제에서 발견한 규칙은 아래와 같다.

1. 빨리 끝나는 회의일수록 뒤에 더 많은 회의를 진행할 수 있다.
2. 뒤에 오는 회의의 시작 시간은 이전 회의의 끝나는 시간과 가장 가까워야 한다.
3. 시작 시간이 같은 경우, 끝나는 시간이 더 빠른 회의가 와야 한다.

from collections import deque
N = int(input()) # 회의 수
time_arr = [] # 시간 배열
result = 0 # 회의 최대 개수

for i in range(N):
    time_arr.append(tuple(map(int, input().split())))

time_arr = sorted(time_arr, key=lambda x: x[1])
tmp = 0

for i in time_arr:
    start_time = i[0]
    finish_time = i[1]

    if start_time >= tmp:
        result += 1
        tmp = finish_time

print(result)

처음에 위와 같이 짰을 땐 결과가 모두 맞게 나와서 정답인 줄 알았는데 오답으로 나왔다. 어떤 문제인가 확인해보니 시작 시간이 같은 경우는 고려하지 않았었다. 시작시간이 같은 경우는 lambda x: x[1], x[0] (x[1]로 오름차순 정렬하고 x[1]이 같은 경우 x[0]으로 오름차순 정렬한다.)과 같이 적어 정렬하면 된다.

from collections import deque
N = int(input()) # 회의 수
time_arr = [] # 시간 배열
result = 0 # 회의 최대 개수

for i in range(N):
    time_arr.append(tuple(map(int, input().split())))

time_arr = sorted(time_arr, key=lambda x: (x[1], x[0])) # 두 번째 원소로 정렬하고 두 번째 원소가 같은 경우 첫 번째 원소로 정렬
tmp = 0

for i in time_arr:
    start_time = i[0]
    finish_time = i[1]

    if start_time >= tmp:
        result += 1
        tmp = finish_time

print(result)