Job Sequencing with Deadlines

We have optional unit-time jobs, each with a deadline and profit, and one machine. A job earns profit only if completed by its deadline. Choose jobs by descending profit and place each accepted job in the latest free slot no later than its deadline. The equal one-unit duration and release-time-zero assumptions are essential: profit-first scheduling is not a generic solution for jobs of arbitrary lengths.

Prerequisites: Ordered Sets; sorting; exchange proofs. Related existing lessons: Sets and Maps.

Build the idea

1. Define discrete slots

   Slots 1…n represent completion times of unit jobs starting at zero. Deadline d allows slots ≤d; d=0 makes a job unschedulable. Clamp large deadlines to n because at most n jobs are executed, and any feasible selected set has a compact schedule within its first n slots. Nonpositive-profit jobs may be skipped since choosing no such job cannot reduce maximum profit.

2. Choose by value, place late

   Sort descending profit and use an ordered set of free slots. upper_bound(min(n,d)) finds the first slot too late; its predecessor, if present, is the latest legal slot. Remove that one iterator and record the job ID at its slot. Placing late preserves early slots for tighter deadlines, unlike simply assigning accepted jobs in profit order from time zero.

   $$\mathrm{slot}=\mathrm{largestFreeTime}\le \mathrm{deadline}$$

3. Correctness proof: lock the greedy placement

   Maintain an optimal schedule agreeing with all previous accepted placements. For the next profitable job G, let s be the latest currently free legal slot. If an optimum already runs G at t, then t≤s because t is not a locked slot; moving G to s and any occupant of s to t preserves deadlines. If G is absent, insert it at s, replacing an unlocked occupant if necessary. That occupant cannot be an earlier rejected higher-profit job: all its legal slots were already locked when it was rejected. Its profit is therefore no larger. If no legal slot exists, G cannot appear in any schedule agreeing with the locked prefix. Induction proves optimality.

4. Trace the sample

   Jobs (deadline,profit) are (2,100),(1,19),(2,27),(1,25). Accept ID 1 in slot 2, then ID 3 in slot 1. Both remaining jobs need slot 1, which is occupied, so reject them. Profit is 127. Notice the execution order is ID 3 then ID 1, although the higher-profit job was considered first.

5. Separate strategy and implementation

   The set supports predecessor queries in O(log n). A later lesson replaces it with a DSU carrying availability metadata, preserving the exact same greedy strategy. Different durations, release times, mandatory jobs, precedence or per-slot profits invalidate parts of this proof and require a new algorithm. The free-slot data structure does not itself guarantee optimality.

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

#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
struct Job{
    int deadline,id;
    long long profit;
};
int main(){
    int n;
    std::cin>>n;
    std::vector<Job>a(n);
    for(int i=0;i<n;++i){
        std::cin>>a[i].deadline>>a[i].profit;
        a[i].id=i+1;
    }
    std::sort(a.begin(),a.end(),[](Job x,Job y){
        return x.profit!=y.profit?x.profit>y.profit:x.id<y.id;
    });
    std::set<int>free;
    for(int t=1;t<=n;++t){
        free.insert(t);
    }
    std::vector<int>schedule(n+1);
    long long profit=0;
    int count=0;
    for(Job j:a){
        if(j.profit>0){
            auto it=free.upper_bound(std::min(n,j.deadline));
            if(it==free.begin()){
                continue;
            }
            --it;
            int slot=*it;
            free.erase(it);
            schedule[slot]=j.id;
            profit+=j.profit;
            ++count;
        } // Latest feasible slot leaves earlier times free.
    }
    std::cout<<count<<' '<<profit<<'\n';
    for(int t=1;t<=n;++t){
        if(schedule[t]){
            std::cout<<t<<' '<<schedule[t]<<'\n';
        }
    }
}

Complexity analysis

O(n log n) sorting, slot-set construction and n predecessor/removal operations. O(n) jobs, slots and output storage. Total profit is at most 10^14 under the input bounds and uses long long.

Example input and output

Read n (0..100000), then deadline profit per job: deadline in 0..10^9, profit in [−10^9,10^9]. Every job lasts one unit and is available at zero. Print selected count and profit, then occupied slot/job-ID pairs in time order.

Input

4
2 100
1 19
2 27
1 25

Output

2 127
1 3
2 1

Profit-first locks job 1 at the latest deadline slot 2, leaving slot 1 for job 3.

Practical applications

Use for optional equal-duration deadline jobs and weighted selection under these exact scheduling constraints. Compare with activity selection’s fixed start/end intervals and with EDD, which orders all jobs to minimize lateness rather than selecting profit.

Check your understanding

Why place an accepted job in the latest free legal slot?

Put it into practice

Compare the selected profit against every feasible subset for at most eight jobs.