[알고리즘] 최대 수입 스케쥴

문제 내용

• 현수는 유명한 강연자이다. N개이 기업에서 강연 요청을 해왔다. 각 기업은 D일 안에 와서 강 연을 해 주면 M만큼의 강연료를 주기로 했다.
• 각 기업이 요청한 D와 M를 바탕으로 가장 많을 돈을 벌 수 있도록 강연 스케쥴을 짜야 한다. 단 강연의 특성상 현수는 하루에 하나의 기업에서만 강연을 할 수 있다.

입력설명

• 첫 번째 줄에 자연수 N(1<=N<=10,000)이 주어지고, 다음 N개의 줄에 M(1<=M<=10,000)과 D(1<=D<=10,000)가 차례로 주어진다.

6
50 2 20 1 40 2 60 3 30 3 30 1

출력설명

• 첫 번째 줄에 최대로 벌 수 있는 수입을 출력한다.

150

구현 방식

• 우선 순위 큐 사용.
• operator< 를 구현할때 맨 마지막 (원소들이 다 동일할때) 예외 케이스를 그냥 true로 리턴하면, 오류가 발생한다..
• 날짜순으로 정렬되어 있는 강의에서 현재 탐색하고 있는 일수에서 들을수 있는 강의들을 최대 힙에 채워준 후, 가장 루트 노드를 채택한다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stack>
#include <numeric>
#include <queue>

using namespace std;
struct Course;
void solution(vector<Course>& courses, int maxDay);

struct Course
{
    Course() {}
    Course(int M, int D)
    {
        this->M = M;
        this->D = D;
    }

public:
    int M;
    int D;
    bool operator<(const Course& c)
    {
        if (this->D != c.D) return this->D < c.D;
        if (this->M != c.M) return this->M < c.M;
        return this->D < c.D;
    }
};

void solution(vector<Course>& courses, int maxDay)
{
    sort(courses.begin(), courses.end());
    int totalMoney = 0;
    priority_queue<int> moneyPQ;
    while (maxDay > 0)
    {
        while (!courses.empty() && courses.back().D >= maxDay)
        {
            moneyPQ.push(courses.back().M);
            courses.pop_back();
        }

        if (!moneyPQ.empty())
        {
            totalMoney += moneyPQ.top();
            moneyPQ.pop();
        }
        
        maxDay--;
    }

    cout << totalMoney;
}