[그리디 알고리즘] 순회강연

예제 입력 1

7

20 1

2 1

10 3

100 2

8 2

5 20

50 10

예제 출력 1

185

 

 

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

2109번: 순회강연

 

- 5일이면 기한이 5일 이후인 모든 강의를 할 수 있다. 따라서 뒷 날짜부터 가능한 강의의 강의료 최대값을 찾아서 더해나가면 된다.

- 문제의 제한인 10000일부터 가능한 강의들을 우선순위 큐에 넣으면 현재 N일일 떄, 가능한 강의들 중 강의료의 최대값을 긁어올 수 있다.

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

class Lecture
{
public:
	int day;
	int pay;

	Lecture()
	{
		day = 0;
		pay = -1;
	}
};
int N;

int main(void)
{
	scanf("%d", &N);
	vector<Lecture> l(N);

	for (int i = 0; i < N; i++)
	{
		scanf("%d %d", &l[i].pay, &l[i].day);
	}
	
	sort(l.begin(), l.end(), [](Lecture u, Lecture v)
		{
			if (u.day == v.day) return u.pay > v.pay;
			return u.day > v.day;
		});

	priority_queue<int> q;
	long long ans = 0;
	int k = 0;

	// 현재 날짜. i일 이면은, 기한이 i일 이상되는 강의이면 다 할 수 있으므로.
	for (int i = 10000; i >= 1; i--)
	{
		while (k < N && i == l[k].day)
		{
			q.push(l[k].pay);
			k++;
		}

		if (!q.empty())
		{
			ans += q.top();
			q.pop();
		}
	}

	printf("%lld\n", ans);

	return 0;
}