[백준/Python] 1931번 : 회의실 배정

1931번: 회의실 배정

시간 제한	메모리 제한	문제 티어
2 초	128 MB	실버 I

📜 문제

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

📥입력

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

 

📤출력

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

 

💡풀이

이 문제는 그리디 알고리즘 문제에 속하며 전에 풀었었던 https://juni-tech.tistory.com/34 문제와 유사하다. 다만 여기서는 한 회의실에서 최대로 할 수 있는 회의의 갯수를 카운팅하는 것에서 약간의 차이가 있다.

 

이 문제의 핵심 포인트는 다음과 같다.

 

1) 끝나는 시간이 빠른 회의를 기준으로 오름차순 정렬

2) 그 다음에 일찍 시작하는 회의를 기준으로 오름차순 정렬

 

먼저 최대한 회의가 일찍 빨리 끝나야 그 다음 더 많은 회의를 할 기회가 생기므로 먼저 앞에 두는 것이 유리하다.

그렇게 한 다음, 그 중에서 끝나는 시간이 같은데 더 일찍 시작하는 회의가 있으면 걔를 앞에다가 둬야 한다. 왜냐하면 이런 반례가 생길 수 있기 때문이다.

input :
3
4 4
4 4
1 4

2)처럼 안할 때:
List : [[4, 4], [4, 4], [1, 4]]
2    # 이렇게 [4, 4] 까지만 카운팅 되고 [1, 4]는 회의실 시간 조건이 안맞게 되어 카운팅 되지 않는다.


2)처럼 할 때 Output이자 정답:
List : [[1, 4], [4, 4], [4, 4]]
3    # 이렇게 해야 [1, 4] -> [4, 4] -> [4, 4] 총 3개의 회의를 진행할 수 있다.

물론 중복해서 회의가 있는데 둘다 동시에 진행된다고 가정하는 것이 이상하겠지만, 이렇게 해야 백준에서는 맞게 채점이 된다...😅

 

다음은 내가 작성한 정답 코드이다.

import sys

input = sys.stdin.readline

N = int(input().rstrip())

room_list = [None] * N

for i in range(N):
  start, end = map(int, input().rstrip().split())
  room_list[i] = [start, end]

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

current = room_list[0][1]
count, index = 1, 0

while index < N-1:
  if current <= room_list[index + 1][0]:
    current = room_list[index + 1][1]
    count += 1
  index += 1

print(count)​