강의실 - [백준 1374번]

강의실 - 백준 1374번

문제

• N개의 강의
• 최대한 적은 수의 강의실을 사용하여 모든 강의 진행
• 한 강의실에서 동시에 강의 진행 불가
• 종료시간과 시작시간이 같아도 상관 없음
• 필요한 최소 강의실의 수 출력

입력

• 첫째 줄 - N : 강의 갯수(1 <= N <= 100,000)
• 둘째 줄부터 각 줄은 순서대로 강의 번호, 강의 시작 시간, 강의 종료시간
• 강의 시작 시간과 강의 종료 시간은 0 이상 10억 이하의 정수

출력

• 첫째 줄에 필요한 최소 강의실 개수 출력

코드

import sys
from queue import PriorityQueue # 우선순위 큐


def countClass(schedules):
  result = 0

  schedules = sorted(schedules, key=lambda s: s['startTime']) # 시작 시간 오름차순으로 정렬

  classes = PriorityQueue() # 우선순위 큐 선언

  for schedule in schedules:
    if not classes.empty() : # 사용하는 클래스가 있다면
      endTime = classes.get() # 클래스 큐 값 반환
      if endTime > schedule['startTime']: # 다음 강의가 가장 빨리 끝나는 클래스의 강의보다 빠르다면
        classes.put(endTime) # 클래스 추가
        result += 1

    else:
      result += 1 # 사용하는 클래스가 없어 결과값 1 추가

    classes.put(schedule['endTime']) # 우선순위 큐에 끝나는 시간 추가

  return result

N = int(sys.stdin.readline()) # 강의의 개수
schedules = []
for _ in range(N):
  number, startTime, endTime = map(int, sys.stdin.readline().split())
  schedules.append({"number": number, "startTime": startTime, "endTime": endTime})
print(countClass(schedules))