백준 파이썬 11000 강의실 배정

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

11000번: 강의실 배정

 

우선순위 큐와 정렬, 그리드 문제

 

수업(queue)을 시작하는 순으로 정렬 후

 

강의실 배열에 수업이 끝나는 시간을 등록하고

만약 다음 수업이 수업의 끝나는 시간보다 일찍 시작한다면 강의실을 또 등록해주면 된다.

다만 이 경우 heapq를 사용하여 우선 순위 큐를 적용하면 된다.

 

그리고 다음 수업이 room 배열에 저장된 숫자보다 크다면(수업이 늦게 시작된다면)

우선 순위 큐를 사용하여 해당 수업을 빼내고 다음 수업의 강의 종료시간을 입력해놓으면 된다.

 

예제 [1,3] [2,4] [3,5] 를 예를 들어서

첫 번쨰 강의실 [3]을 등록, 전체 큐 [3]

두 번쨰 강의실 [4]를 등록 전체 큐 [3,4]

첫 번째 강의를 이어가서 [3]을 빼내고 [5]를 추가, 전체 큐 [4,5]

 

답은 len(room) = 2

 

또한 N의 수가 200,000 이므로 input을 사용하면 시간초과가 난다. ㅜ 당했음

 

import heapq
import sys
input = sys.stdin.readline

n = int(input())

queue = []

for i in range(n):
    a,b = map(int,input().split())
    queue.append([a,b])

queue.sort()

room = []

heapq.heappush(room,queue[0][1])

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

    else:
        heapq.heappop(room)
        heapq.heappush(room,queue[i][1])

print(len(room))