[BOJ] 11000번 강의실 배정

[BOJ] 11000번 - 강의실 배정

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

11000번: 강의실 배정

 

 

알고리즘

---

그리디를 이용한 알고리즘으로 생각하여 풀었습니다.

가정) 현재까지의 강의실 시간 중에 가장 빨리 끝나는 시간보다 늦게 끝난다면, 현재 강의실에 이어서 하면 된다.

아니라면 강의실 추가

 

1. 강의실 시간을 시작 시간 , 끝나는 시간으로 재정렬

2. 순차적으로 강의실 시간을 보면서 현재까지의 가장 빨리 끝나는 시간과 비교

3-1. 만약 빨리 끝나는 시간보다 시작한 시간이 더 작다면, 강의실이 추가적으로 필요

3-2. 시간이 더 크다면, 현재 강의실에 이어서 처리하면 된다.

4. 현재까지의 강의실 갯수를 출력

 

코드

---

#BOJ 11000번

import sys
input = sys.stdin.readline
import heapq

n = int(input())
datas = [ tuple( map(int,input().split())) for _ in range(n) ]
datas.sort()
q = []

for data in datas :
    if q :
        top = heapq.heappop(q)
        if top[0] > data[0] :
            heapq.heappush( q , top )
    heapq.heappush( q , (data[1] ,data[0]) )

print( len(q) )