[그리디/구현] 백준 11000: 강의실 배정 (python)

https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

 

 
강의의 시작-끝 시간이 주어지고 강의실을 배정하여 최소 강의실 수를 찾는 문제
레벨을 모르고 선택했다가 레벨과 정답률을 보고 주춤한 문제.
 
처음 생각)
강의 시작시간과 끝 시간을 리스트에 받아서, [[1,3],[2,4],[3,5]] 회의 시작시간에 따라 오름차순으로 정렬한다.
i 번째 강의 끝시간 > i+1 번째 강의 시작시간이면 새로운 강의실을 추가하여 사용하도록 해야한다는 생각이 들었다.
 
이 문제에서 주의해야할 점은 다른 그리디 강의실 배정 문제처럼 강의가 빨리 끝나는 순으로 정렬한다는 생각에 사로잡히면 문제를 풀기 어려워지는 것 같다.
그리고 heap 자료구조를 사용하여 보다 간단하게 해결할 수 있었다..!
 

import heapq

N = int(input("강의실의 개수를 입력하세요: "))
lecture = sorted([list(map(int, input().split())) for _ in range(N)])
room = []
heapq.heappush(room,lecture[0][1])

for i in range(1,N):
    if lecture[i][0] < room[0]:
        heapq.heappush(room, lecture[i][1])
    else:
        heapq.heappop(room)
        heapq.heappush(room, lecture[i][1])

print(len(room))

근데 시간초과가 났습니다 이런. 나도 프로그래머스로 풀래
 

import sys, heapq

N = int(sys.stdin.readline())

# 강의 정보를 리스트로 받아서 시작 시간을 기준으로 정렬
lecture = sorted([list(map(int, sys.stdin.readline().split())) for _ in range(N)])

# 강의실을 관리할 힙(heap) : 종료시간 기록
room = []

# 첫 번째 강의의 종료 시간을 힙에 추가
heapq.heappush(room, lecture[0][1])

for i in range(1, N):
    # 만약 현재 강의의 시작 시간이 가장 빨리 끝나는 강의의 종료 시간보다 빠르다면
    if lecture[i][0] < room[0]:
        # 새로운 강의실 할당
        heapq.heappush(room, lecture[i][1])
    else:
        # 그렇지 않다면 해당 강의실을 빼내고 현재 강의의 종료 시간을 힙에 추가
        heapq.heappop(room)
        heapq.heappush(room, lecture[i][1])
print(len(room))