[BOJ] 1781번: 컵라면

https://www.acmicpc.net/problem/1781

일단, 기본적으로 선택할 수 있는 숙제 중에 가장 컵라면을 많이 주는 것을 선택하는 것이 좋습니다. 그러나 Deadline으로 인해 굉장히 복잡하게 되는데, 관점을 살짝 달리해 절대 선택될 수 없는 컵라면을 버리고 가는 식으로 처리할 수 있습니다.

예를 들어

7

3 1

3 2

3 3

3 4

3 5

3 6

7 4

인 경우, 우리는 (3 1), (3 2), (3 3)은 무시해도 됨을 알 수 있습니다. 이걸 코드로 자연스럽게 하는 방법은, 숙제를 deadline순으로 정렬한 뒤, 각 숙제애 대해 우선 priority queue에 보상을 삽입합니다. 만약 priority queue에 현재 deadline보다 더 많은 원소가 들어있을 경우 deadline과 같아질 때 까지 원소를 제거합니다. 다 끝난 이후에 priority queue에 남아있는 보상의 합이 정답입니다.

https://github.com/blisstoner/BOJ/blob/master/1781.cpp