1931: 회의실 배정

 

처음에는 각 회의 정보를 회의 시간(시작 시간 - 끝난 시간) 기준으로 정렬해서 문제를 풀었었다.

하지만 오답 처리 되었고 반례를 찾아본 결과 회의 시간이 적다고 해서 무조건 최대로 배정할 수 있는게 아니었다.

반례로 1, 7 / 7, 10 / 6, 8 정도를 들어볼 수 있다.

회의 시간이 제일 적은 것은 6, 8 지만 6, 8를 선택하는 대신 1, 7과 7, 10으로 2개의 회의 시간만큼을 배치할 수 있다.

따라서 회의 시간 대신 끝나는 시간 순으로 오름차순 정렬을 해서 문제를 풀었다.

하지만 그래도 자꾸 시간 초과되는 문제가 있었는데 N이 100,000 까지 들어올 수 있는 문제에서

O(n^2)로 코드를 구현했기 때문이었다.

기존 O(n^2) 코드는 별도에 리스트를 두고 선점한 회의 시간을 표기하는 방식이었는데

정렬을 하고 차례대로 처리해나가면 별도로 선점한 회의 시간을 표기할 필요가 없다는 것을 깨닫고

코드를 간결하게 수정할 수 있었다.

 

n = int(input())
 
result = 0
end_time = 0
room_list = list()
 
for i in range(n):
  s, e = map(int, input().split())
  room_list.append((s, e))
 
room_list.sort(key=lambda x:(x[1], x[0]))
 
for room in room_list:
  s, e = room
  if end_time <= s:
    result += 1
    end_time = e
 
print(result)