[Level3] 강의실 배정

강의실 배정 문제 링크

🌟문제

김교수는 강의실 1개에 최대한 많은 강의를 배정하려고 한다. 배정된 강의는 서로 겹치지 않아야 하며 수업시간의 길이와 상관없이 최대한 강의를 많이 배정하라. 단, 두 강의의 시작시간과 종료시간은 겹쳐도 된다.

솔직히 sort를 써도 잘 해결이 되는데, 시간초과가 나서 heapq로 풀었다. 근데 시간초과는 안나지만 테스트 케이스 5, 6, 9, 10이 안풀려서 힘들었던 문제😥

😠 코드 리뷰 - Sort (시간초과)

Sort를 쓰면 코드는 잘 작동하고, 심지어 시작시간과 종료시간도 알아서 정렬해준다. 하지만 시간초과로 실패

import sys
input = sys.stdin.readline

n = int(input())
arr = []
for _ in range(n):
    arr.append(list(map(int,input().split())))
arr.sort()
cnt = 0
now = 0
for a in arr:
    if now <= a[0]:
        cnt +=1
        now = a[1]
print(cnt)

Heapq (힙큐)

heapq 에 튜플이 삽입될 경우엔, 튜플의 첫 번째 요소가 정렬의 기준이 됩니다.

• heapq.heappush(heap, item) : item 값을 heap으로 푸시

• heapq.heappop(heap) : heap에서 가장 작은 항목을 팝하고 반환합니다. 힙이 비어 있으면, IndexError가 발생합니다. 팝 하지 않고 가장 작은 항목에 액세스하려면, heap[0]을 사용

힙큐는 보통 리스트처럼 크기 순서대로 정렬되지 않는다. 예를들어 [12,0,9,27] 이라는 리스트를 heapify를 사용해 힙 자료형으로 만들어도 정렬이 되지 않는 모습을 볼 수 있다.
arr[0]을 이용해 최솟값을 출력할 수 있다.

📑 알고리즘

• 튜플로 (종료시간, 시작시간)을 힙큐에 push
• 종료시간을 기준으로 정렬
• 꺼낸 값의 시작시간은 그전에 종료시간보다 크거나 같으면 카운터

😠 코드 리뷰 - 틀린코드

for f,s in arr:
    if s >= now: 
        now = f
        ans += 1

여기서 arr는 (종료시간,시작시간)으로 정렬된 힙큐인데, 그냥 단순히 arr 원소값을 차례대로 탐색한다면 더 뒤에 있는 최소시간을 못 빼주기 때문에(당연함), heappop을 이용해 최솟값을 빼준다.

반례

6
3 5
1 3
1 2
1 4
2 4
2 3
// 답==3

😊 전체 코드

import sys
import heapq
input = sys.stdin.readline

n = int(input())
arr = []
for _ in range(n):
    a, b = map(int,input().split())
    heapq.heappush(arr,(b,a))

ans = 0
now = 0

while arr:
    a,b = heapq.heappop(arr)
    if b >= now: 
        now = a
        ans += 1

print(ans)