백준 11000 : 강의실 배정 ( Python )

문제 링크

📌 사용 알고리즘 : priority queue , 정렬

문제는 간단합니다. 수업을 진행할것인데 최소강의실로 모든 수업을 해야합니다.

다만 1~2 와 2~3 일때는 강의실 하나면 됩니다.

• 4
1 20
2 4
3 9
4 5

이런 입력을 생각해봅시다. 답은 일단 3 입니다.

일단 가장 기본적인 접근방법은 정렬입니다.

강의가 시작되는 수업먼저 정렬해두면 시작되는 시간은 신경쓰지 않아도 됩니다.

다만 끝나는 시간 처리가 까다롭습니다.

1~20 강의 도중에 2~4 강의가 들어옵니다. 또 3~9 강의가 들어옵니다.

시작시간은 신경쓰지 않아도 되므로 만약 현재시간이 3 일때 곧 끝날 강의는 20 , 4 , 9 가 됩니다.

그다음에 시간이 4 가 될때 4~5 강의가 들어옵니다.

이때 끝날 강의중 20,4,9 에서 2~4 강의가 끝나게 됩니다. 이를 처리해줘야 하는데
직접 구현해보면 단순히 start , end 변수 두개만으로는 관리가 힘듭니다.
왜냐하면 끝나는 강의는 정렬되지 않은 상태로 존재하기 때문입니다.

그렇다고 끝나는 강의들의 목록을 배열로 관리하자니 매번 정렬을 꼭 해줘야 합니다.
정렬을 하지 않으면 다음 강의가 끝날 최소값을 구하지 못합니다. 이러면 최소 강의실의 개수를 구할 수 없습니다.
하지만 시간복잡도가 O(N^2logN) 이 되어버립니다.

매번 배열에 원소가 추가되면서 정렬상태가 유지되어야하고 , 시간복잡도가 적은 방법이 무엇이 있을까요? 바로 우선순위 큐 입니다.

삽입과 삭제가 O(logN) 이므로 시간복잡도는 O(NlogN) 만으로 문제를 해결할 수 있습니다.
먼저 배열을 시작시간을 오름차순으로 , 끝나는시간을 내림차순으로 정렬해줍니다.
그리고 매번 힙에다가 강의의 시작시간과 끝나는 시간을 넣고 다음 강의가 시작되는 시간보다 이전의 강의가 끝나는 시간이 더 짧으면 그 강의를 지워줍니다.

이때 힙의 최대 길이가 정답이 됩니다.

📌 코드

import sys,math,heapq
input=sys.stdin.readline
from functools import lru_cache
from collections import deque
LMI=lambda:list(map(int,input().split()))
LMS=lambda:list(map(str,input().split()))
MI=lambda:map(int,input().split())
I=lambda:int(input())
GI=lambda x:[ LMI() for _ in range(x) ]
GS=lambda x:[ LMS() for _ in range(x) ]
V=lambda x,y:[ [False]*y for _ in range(x) ]

N = I()
graph = GI(N)

graph.sort(key=lambda x:(x[0],-x[1]))
ans = 1
heap=[]

for i in range(len(graph)):
    heapq.heappush(heap , graph[i][1])

    while heap and graph[i][0]>=heap[0]:
        heapq.heappop(heap)
    ans = max(ans , len(heap))

print(ans)