Greedy with Priority Queues

A heap answers which candidate is best now, but the greedy proof must explain why choosing that candidate is safe. We schedule optional unit jobs on days 1…D. Each job has a release day and a fixed profit, with no individual deadline other than the common final horizon. Processing days in order, insert newly released jobs and take the highest-profit eligible job. Future jobs must not enter the heap early.

Prerequisites: Priority Queues; release times; exchange arguments. Related existing lessons: Priority Queues and Binary Heaps.

Build the idea

1. Separate eligibility and priority

   Sort jobs by release day. For a day d, add every job with release≤d that has not yet entered the heap. The max-heap orders these candidates by profit, then smaller ID. This is different from a single global profit sort, which might choose a profitable job before it is released. Nonpositive-profit jobs may be skipped because the empty day is allowed and gives zero profit.

2. Maintain the day invariant

   At the start of selection, the heap contains exactly the positive-profit released jobs not previously executed. Pop at most one, record its ID, and advance to the next day. When the heap is empty, leave a zero in the schedule. A job may wait after release because there is no per-job expiration or deadline; that assumption keeps all heap entries eligible on later days.

   $$\mathrm{choose}\mathrm{maxProfit}\mathrm{among}\{\mathrm{release}\le \mathrm{day}\mathrm{and}\mathrm{unused}\}$$

3. Correctness proof: exchange an available job

   Consider an optimum agreeing with the already fixed greedy days. On the next day greedy chooses available job G of maximum profit. If the optimum executes G later, swap G with its current-day job J: J was available today, so it is also available on that later day. If G is absent, replace today’s job or idle slot by G; its profit is no smaller. Future unreleased jobs are unaffected. Thus an optimum can agree with this day, and induction proves the entire schedule optimal.

4. Trace the sample

   Three days and jobs (release,profit)=(1,5),(1,10),(2,8),(3,20). Day 1 chooses ID 2 for 10, leaving ID 1 available. Day 2 adds ID 3 and chooses it for 8. Day 3 adds ID 4 and chooses it for 20. Total profit is 38 with IDs 2,3,4. Choosing the unreleased ID 4 on day 1 would violate the model.

5. Know the heap’s limits

   If jobs had different durations, choosing one would consume unequal capacity and the exchange would not preserve a day slot. If individual deadlines existed, a lower-profit urgent job might need to run now while a higher-profit one could wait. The priority queue does not detect that modeling error. Here release-only unit jobs and a common horizon provide the safe exchange.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<utility>
struct Job{
    int release,id;
    long long profit;
};
int main(){
    int n,days;
    std::cin>>n>>days;
    std::vector<Job>jobs(n);
    for(int i=0;i<n;++i){
        std::cin>>jobs[i].release>>jobs[i].profit;
        jobs[i].id=i+1;
    }
    std::sort(jobs.begin(),jobs.end(),[](Job a,Job b){
        return a.release!=b.release?a.release<b.release:a.id<b.id;
    });
    std::priority_queue<std::pair<long long,int>>eligible;
    std::vector<int>schedule(days);
    long long total=0;
    int i=0,count=0;
    for(int day=1;day<=days;++day){
        while(i<n&&jobs[i].release<=day){
            if(jobs[i].profit>0){
                eligible.push({jobs[i].profit,-jobs[i].id});
            }
            ++i;
        }
        if(!eligible.empty()){
            total+=eligible.top().first;
            schedule[day-1]=-eligible.top().second;
            eligible.pop();
            ++count;
        }
    } // Never select an unreleased job.
    std::cout<<total<<' '<<count<<'\n';
    for(int d=0;d<days;++d){
        std::cout<<schedule[d]<<(d+1==days?'\n':' ');
    }
    if(days==0){
        std::cout<<'\n';
    }
}

Complexity analysis

O(n log n) sort and O(n log n+days) sweep/heap work; every inserted job is popped at most once. O(n+days) storage including the reconstructed schedule. Profit≤10^14 uses long long. Iterating days is intentional under the 100000-day contract.

Example input and output

Read n days (0..100000 each), then release profit per unit job. Release in 1..10^9, profit in [−10^9,10^9]. Jobs remain available after release; one per day, common horizon. Print profit/count, then one job ID per day (0 means idle).

Input

4 3
1 5
1 10
2 8
3 20

Output

38 3
2 3 4

The best currently eligible profits are 10,8,20; the profit-5 job remains unused.

Practical applications

Use heaps when the best eligible candidate changes as time or reach expands. Refueling prioritizes largest additive fuel; merge patterns prioritize two smallest weights. The data structure is shared, but each problem needs its own objective and proof.

Check your understanding

Why may the swapped current-day job run on a later day in the proof?

Put it into practice

Enumerate every small day-to-job assignment and compare profits.