[BOJ / python] #1202 보석 도둑 그리디

import sys
import heapq

n,k = map(int,sys.stdin.readline().split())

x=[list(map(int,sys.stdin.readline().split())) for i in range(n)]
y=[int(sys.stdin.readline()) for i in range(k)]
x.sort(key=lambda x: x[0])
y.sort()
i=0
j=0
heap=[]
ans=0

while i < k:
    while j < n:
        if y[i]>=x[j][0]:
            heapq.heappush(heap,-x[j][1])
            j+=1
        else:
            break
    i+=1
    if heap: // 이 부분 추가
        ans+=-heapq.heappop(heap)

print(ans)

 

heap을 쓰지 않고 그냥 리스트로 구현하니 런타임 에러가 나서 heap을 넣고 구현하였다. 파이썬에서 heap은 최솟값으로 정렬되기 때문에 값에 -를 붙여서 answer를 구할 때 다시 -를 붙여줬다. 위 코드에서 heap이 비었을 때를 추가해주어야 테스트 케이스가 통과된다.