[Python 알고리즘] 백준 1931번 : 회의실 배정

문제

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

입력

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

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

출력

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

# Case 1
4

내가 제출한 풀이 - 정답

import sys

n = int(sys.stdin.readline().strip())
n_list = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]


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

end = n_list[0][1]
res = (0 if n_list[0][0] == n_list[0][1] else 1)

for item in n_list:
    if end <= item[0]:
        end = item[1]
        res += 1

print(res)

Tip

종료시간 기준으로 오름차순 정렬하여 푸는 간단한 문제였다. 종료시간을 정렬하여 가장 먼저 끝나는 시간을 확인 후 그걸 가지고 있다가 다음 회의를 차례대로 봐 풀면 되는 문제였다.

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

저번 강의실 배정이랑 같은 맥락이라고 봐도 된다. x[1] : 종료시간을 기준을 잡되, 만약 종료시간이 같다면 시작시간 기준으로 정렬을 하는 것이다.

"""
    입력 :
    11
    1 4
    3 5
    2 5
    5 7
    3 8
    5 9
    6 10
    8 11
    8 12
    2 13
    12 14
"""

# lambda x: x[1] = 종료시간 기준
[[1, 4], [3, 5], [2, 5], [5, 7], [3, 8], [5, 9], [6, 10], [8, 11], [8, 12], [2, 13], [12, 14]]

# lambda x: (x[1], x[0]) = 우선순위 1. 종료시간 2. 시작시간
[[1, 4], [2, 5], [3, 5], [5, 7], [3, 8], [5, 9], [6, 10], [8, 11], [8, 12], [2, 13], [12, 14]]

종료시간 기준으로만 보게 된다면 [3, 5]가 [2, 5]보다 빨리 들어오게 된다면 제대로 된 정렬이 되지 않는다.

그래서 종료시간과 시작시간을 둘 다 사용하여 정렬하게 되면 [3, 5]가 [2, 5] 뒤로 들어오게 된다.

res = (0 if n_list[0][0] == n_list[0][1] else 1)

"""
    1, 1 : if 1 <= 1은 True이기 때문에 +1
    1, 3 : if 1 <= 3은 False이기 때문에 +1을 하지 않았음.
    
    처음 강의실을 배정 받았을 때는 무조건 +1을 해줘야하기 때문
"""

입력에서 시작 시간과 종료 시간이 같은 게 들어오게 된다면 정상적으로 회의실 개수를 1개 늘리지만 다르게 된다면 회의실 개수를 1개 늘리고 시작하지 않게 된다.