회의실 배정 - 1931

1931번: 회의실 배정

회의의 시작 시간과 끝나는 시간이 적힌 리스트가 주어졌을 때,

최대로 사용할 수 있는 회의의 최대 개수를 구하는 문제이다.

시행 착오 1 🥲

먼저 회의가 끝나는 시간을 기준으로 정렬해서 회의를 순차적으로 선택하는 방식으로 구현했는데 일부 케이스에서 틀렸다는 결과가 나왔다.

이유를 고민해봤는데 회의가 시작하는 시간과 끝나는 시간이 같은 경우, 해당 시간대에 회의를 2개 선택할 수 있다는 점을 고려하지 못했다. 위에서 보면, $(10, 10)$ 뒤에 $(8, 10)$이 오는 경우, 두 개 모두 선택할 수 있지만 알고리즘은 $(10, 10)$을 먼저 택하기 때문에 뒤에 오는 $(8, 10)$를 선택하지 못하게 된다.

그래서 이 부분을 반영하기 위해서는 시작 시간 기준으로 먼저 정렬을 하고, 그 뒤에 끝나는 시간 기준으로 정렬을 해주면 예외 상황을 해결할 수 있다!

맞았습니다! 풀이

시작 시간 기준 정렬을 추가해주었더니 풀렸다.

n = int(input())
time = [list(map(int, input().split())) for _ in range(n)]

time.sort(key=lambda x: x[0])  # 시작시간 기준 정렬 (추가!)
time.sort(key=lambda x: x[1])  # 끝 시간 기준 정렬

count, temp = 0, 0
for start, end in time:
  if temp <= start:
    count += 1
    temp = end
print(count)

맨 위로 이동하기