1374 백준 파이썬

처음에는 dfs로 해결하려 했지만, 시간 초과에 부딪혔다.

답은 우선순위 큐였다. 하나만 쓸려다가 계속 막혔는데 두개를 써보니 해결됐다.

 

우선순위 큐에서 꺼내면서 그 값의 end값을 q안에 push한다. 그리고 end값과 q[0]을 비교하고, 만족했을 때 그값을 빼내면 된다. 비교했을때 만족하지 못해도 그냥 q에 넣는다. 마지막엔 q에 남아있는 값의 수를 출력해주면 된다.

#https://www.acmicpc.net/problem/1374
import sys
import heapq
input=sys.stdin.readline
n=int(input())
lecture=[]
q=[]
for _ in range(n):
    l=list(map(int,input().split()))
    heapq.heappush(lecture,[l[1],l[2],l[0]])
start, end, no=heapq.heappop(lecture)
heapq.heappush(q,end)
while lecture:
    start, end, no=heapq.heappop(lecture)
    if q[0]<=start:
        heapq.heappop(q)
    heapq.heappush(q,end)
print(len(q))