[Softeer/Python] 강의실 배정 ★★★☆☆ - 효과는 굉장했다!

Softeer

 

SOLUTION

 

※ 실패한 코드

lambda를 이용해 정렬을 하는 코드를 짜는데 시간초과의 문제가 발생했다.

import sys

N = int(sys.stdin.readline())
meeting_time = [[0] * 2 for _ in range(N)]
for i in range(N):
    start, end = map(int, sys.stdin.readline().split())
    meeting_time[i][0] = start
    meeting_time[i][1] = end

meeting_time.sort(key=lambda x : [x[1], x[0]]) # 시간초과의 원인

end_time = meeting_time[0][1]
cnt = 1

for i in range(1, N):
    if meeting_time[i][0] >= end_time:
        cnt += 1
        end_time = meeting_time[i][1]
        
print(cnt)

 

※ 성공한 코드

heapq 모듈을 사용하여 정렬을 사용하지 않고 heappush를 사용함으로써 시간 단축을 할 수 있었다.

import sys
import heapq

N = int(sys.stdin.readline())
meeting_time = []

for _ in range(N):
    start, end = list(map(int, sys.stdin.readline().split()))
    # 끝나는 시간이 가장 작은 것을 맨 앞에 넣어준다, 만약 시작 시간이 같을 때에는 가장 작은 시간부터 오름차순으로
    heapq.heappush(meeting_time, (end, start)) 

end_time = 0
cnt = 0

while meeting_time:
    if meeting_time[0][1] >= end_time:
        end_time = heapq.heappop(meeting_time)[0]
        cnt += 1
        continue

    heapq.heappop(meeting_time)

print(cnt)