[백준] 11000 강의실 배정 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/11000
• 그리디, 정렬, 우선 순위 큐

 

import sys
from heapq import heappush, heappop
input = sys.stdin.readline

n = int(input())

lst = [list(map(int, input().split())) for _ in range(n)]   # s에 시작 t에 끝나는 수업 [s, t]
lst.sort()  # 수업 시작 시간으로 정렬

room = []
heappush(room, lst[0][1]) # 첫 강의 끝 시간

for i in range(1, n):
    if lst[i][0] < room[0]:     # 다음 수업 시작 시간이 현재 수업 종료 시간보다 작으면 (강의 중이면)
        heappush(room, lst[i][1])   # 힙에 다음 수업 종료 시간 추가 (다른 강의실 써야한다.)
    else:   # 다음 수업 시작 시간이 현재 수업 종료 시간보다 크거나 같으면 같은 강의실 쓸 수 있다. (강의가 끝났으면)
        heappop(room)   # 종료된 수업 빼
        heappush(room, lst[i][1])   # 다음 수업 종료 시간 추가

print(len(room))