https://www.acmicpc.net/problem/1374
1374번: 강의실첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의www.acmicpc.net
처음에는 걍 싹다비교해봤는데, 당연히 시간초과가 났다.
이런류의 문제는 거의 처음 접해봐서, 힌트를 얻고 풀었다.
먼져, 강의를 시작시간 순으로 정렬해준다.
이후 끝나는 시간 순으로 힙을 만들어준다
정렬해 놓은 강의들을 하나씩 비교하는데
만일 강의의 시작시간이 힙의 첫번째원소, 즉 가장 빨리 끝나는 강의보다 크다면
어쩔 수 없이 강의실을 하나 더 만들어야된다
그게 아니라면, 가장 빨리 끝나는 강의를 pop해주고
지금 보고 있는 강의를 힙에 넣어준다면,
힙의 성질에 의해서 가장 빨리 끝나는 강의가 루트로 올 것이다.
이후 힙의 갯수를 세면 된다.
import sysimport heapqinput = sys.stdin.readline
lect, h = [], [] #강의들(시작시간기준) , 강의실(끝나는시간 기준)answer = []n = int(input())
for _ in range(n): # 강의를 시작하는순서대로 정렬 a, b, c = map(int, input().split())
heapq.heappush(lect, (b, c))
heapq.heappush(h, heapq.heappop(lect)[1]) #가장 빨리 시작하는 강의를 강의실에 배정while lect:
start, end = heapq.heappop(lect)
if start >= h[0]: #만일 가장 빨리끝나는강의실보다 같거나 늦게 시작한다면,
heapq.heappop(h) #가장빠른강의실에
heapq.heappush(h, end) #새로운강의를 배치함 heap성질에 의해서 정렬될것임
else: #만일 가장 빨리끝나는강의실보다 빨리 시작한다면 heapq.heappush(h, end) #새 강의실을 배정해야함
print(len(h))