Job Sequencing with Deadlines: given n jobs each with a deadline and profit, schedule jobs (each taking one unit time) to maximize total profit. The greedy approach sorts jobs by profit descending and assigns each job to the latest available slot before its deadline. Uses a Union-Find for efficient slot finding.
int jobSequencing(vector<tuple<int,int,int>>& jobs) {
sort(jobs.begin(),jobs.end(),[](auto&a,auto&b){return get<2>(a)>get<2>(b);});
int maxDeadline=0;
for(auto&[id,d,p]:jobs) maxDeadline=max(maxDeadline,d);
vector<int> slot(maxDeadline+1,-1); int profit=0;
for(auto&[id,d,p]:jobs)
for(int j=min(d,maxDeadline);j>0;j--)
if(slot[j]==-1){slot[j]=id;profit+=p;break;}
return profit;
}Sort jobs by profit descending. For each job, try to schedule it in the latest available slot before its deadline. This greedy choice ensures we always pick the most profitable jobs first.
For each job with deadline d, scan time slots from d down to 1. Assign the job to the first empty slot found. If no slot is available before the deadline, the job is skipped.
Naive slot search is O(n) per job. Using Union-Find, each slot points to the next available slot, giving near O(1) per lookup and total O(n log n) complexity.
Quiz coming soon for this algorithm.