[BOJ]11000_강의실배정

✔️문제 링크

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

💡핵심 아이디어

1️⃣ 강의 시작시간을 오름차순으로 정렬 후 시작 시간이 빠른 순서대로 끝나는 시간을 heapq에 넣어준다.

2️⃣ 다음 강의를 고려 시 현재 진행되고 있는 강의의 끝나는 시간들 중 가장 작은 수보다 큰 수이면 heapq에서 pop을 하고 해당 강의실을 쓴다고 고려하고 그렇지 않으면 새로운 강의실을 배정한다고 생각하고 그냥 heapq에 강의가 끝나는 시각을 넣어준다.

3️⃣ heapq에 들어있는 원소의 개수가 강의실을 사용한 수가 된다.

⭐️소스 코드

import sys
import heapq
input = sys.stdin.readline

if __name__ == '__main__':
    N = int(input())
    class_list = []
    heap = []

    for _ in range(N):
        s, t = map(int, input().split())
        class_list.append([s,t])

    # 강의의 시작 순으로 정렬
    class_list = sorted(class_list, key = lambda x : x[0])

    heapq.heappush(heap,class_list[0][1])

    # 순회하며 끝나는 시각을 heapq에 저장
    for info in class_list[1:]:
        s, t = info
        check = heap[0]

        # 만약 강의가 끝나는 시각이 아니라면
        if check > s:
            heapq.heappush(heap, t)
        else:
            heapq.heappop(heap)
            heapq.heappush(heap, t)

    print(len(heap))