문제 링크

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

문제 설명

• 수업 시작 시간, 종료 시간 리스트가 주어짐
• 최소 강의실 개수 출력

풀이

• 우선순위 큐에 강의실의 마지막 수업 종료 시간을 저장한다
• 수업 시작 시간의 오름차순으로 가능한 강의실이 있는지 검사한다
• 해당 시작 시간보다 작은 종료 시간이 있다면
  • 갱신
• 없다면
  • 강의실 추가
• 큐의 원소 개수 출력

후기

• 어려웠다..
• 처음에 이분 탐색으로 풀어봤는데 80퍼쯤 시간 초과가 났다
  • 최악에 O(N^2)이 되는듯

코드

import sys, heapq


def solution():

    # 입력 받기
    read = sys.stdin.readline
    n = int(read())
    lectures = [list(map(int, read().split())) for _ in range(n)]
    lectures.sort()

    # 각 강의실의 마지막 종료 시간만 저장
    hq = []
    heapq.heappush(hq, lectures[0][1])

    # 수업의 시작 시간 순으로 탐색
    for i in range(1, n):
        # 강의실 중 최소 종료 시간보다 시작 시간이 클 때
        if hq[0] > lectures[i][0]:
            # 강의실 추가
            heapq.heappush(hq, lectures[i][1])
        # 빈 강의실이 있을 때
        else:
            # 해당 강의실 종료 시간 갱신
            heapq.heappop(hq)
            heapq.heappush(hq, lectures[i][1])

    print(len(hq))


solution()