[백준/Python] 11000번 - 강의실 배정

문제

백준 11000번 - 강의실 배정

해결 과정

• 아이디어: 우선순위 큐
  • 비교해서 넣었다가 빼고 하는 문제는 큐? 스택? 🙄
• 현재 회의실의 종료 시간과 다음 열릴 회의의 시작 시간과의 관계
  1. 현재 회의실의 종료 시간보다 다음 회의의 시작 시간이 빠르다면
     = 현재 회의실 종료 시간 > 다음 회의 시작 시간
     회의실을 추가로 개설
  2. 현재 회의실의 종료 시간보다 다음 회의 시작 시간이 같거나 느리다면
     = 현재 회의실 종료 시간 <= 다음 회의 시작 시간
     현재 회의실에서 이어서 회의
• time : [시작 시간, 종료 시간]을 리스트에 넣어준다.
• time.sort() : 시작시간을 기준으로 오름차순으로 정렬
• 큐에 제일 일찍 시작하는 회의의 종료 시간을 넣어준다.
• for문: 두 번째 회의부터 마지막 회의까지
  • i번째 회의 시작 시간이 현재 회의실의 종료 시간보다 빠르다면
    회의실을 추가해준다 = 큐에 i번째 회의의 종료 시간을 넣어준다.
  • i번째 회의 시작 시간이 현재 회의실의 종료 시간보다 느리거나 같다면
    해당 회의실에 이어서 회의를 한다 = 들어가있던 회의를 빼고 i번째 회의의 종료 시간을 넣어준다.
• room의 길이 반환

풀이

import sys
import heapq

n = int(sys.stdin.readline())
time = [[] for _ in range(n)]

for i in range(n):
    time[i] = list(map(int, sys.stdin.readline().split()))

time.sort()


room = []
heapq.heappush(room, time[0][1])

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

print(len(room))