Greedy with Disjoint Set Union

DSU can accelerate a greedy algorithm’s bookkeeping without changing why its choices are optimal. We revisit unit-time deadline jobs: descending profit chooses the job, while DSU finds the latest available completion slot. To retain both path compression and union-by-size guarantees, the representative ID is not treated as the answer. Separate component metadata stores the leftmost—and still available—slot.

Prerequisites: Job Sequencing with Deadlines; Disjoint Set Union. Related existing lessons: Disjoint Set Union (DSU).

Build the idea

1. Understand the component invariant

   Initially every slot 0…n is its own component, with leftmost equal to its index. Slot 0 is a failure sentinel and is never occupied. A component is a consecutive run whose leftmost slot is free and whose later slots have already been used. Therefore the latest free slot at or before d is leftmost[find(d)]. Clamp d to n as in the earlier scheduling lesson.

2. Delete an available slot by union

   When slot s>0 is chosen, mark it occupied and merge its component with the component containing s−1. The new leftmost is the minimum of both metadata values. The union root is selected by component size, not by numeric index; this keeps trees shallow. Path compression rewrites search paths while preserving component membership and metadata at the representative.

   $$\mathrm{latestFree}\left(d\right)=\mathrm{leftmost}\left[\mathrm{find}\right(d\left)\right]$$

3. Correctness proof: data structure plus greedy theorem

   The component invariant holds initially. Occupying its only free slot and joining the predecessor component creates another consecutive run with exactly the predecessor’s free slot, so the minimum metadata is correct. No slot is returned twice, and zero precisely signals no legal slot. Thus DSU supplies the same latest-free choices as the ordered-set job sequencer. Its optimality proof still comes from locking profit-first latest-slot placements and exchanging an optimum to agree, under unit durations and release time zero. Faster find operations do not make a different scheduling model greedy-correct.

4. Trace the same schedule

   Jobs (2,100),(1,19),(2,27),(1,25) first query slot 2 and occupy it, merging with slot 1. The next deadline-2 query follows that component and returns 1; occupying it merges with sentinel 0. Later deadline-1 queries return 0 and are rejected. The result remains count 2,profit 127, with IDs 3 and 1 in slots 1 and 2.

5. Distinguish other DSU uses

   In Kruskal, DSU asks whether two graph endpoints already share a component; here it represents deleted choices and predecessor availability. A naive forced-parent deletion structure is common, but one must not quote the union-by-rank inverse-Ackermann theorem without its required balancing. This version explicitly uses size and separate minimum metadata, so the standard amortized DSU bound applies.

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

#include<iostream>
#include<vector>
#include<numeric>
#include<algorithm>
struct DSU{
    std::vector<int>parent,size,leftmost;
    explicit DSU(int n):parent(n+1),size(n+1,1),leftmost(n+1){
        std::iota(parent.begin(),parent.end(),0);
        std::iota(leftmost.begin(),leftmost.end(),0);
    }
    int find(int x){
        return parent[x]==x?x:parent[x]=find(parent[x]);
    }
    void unite(int a,int b){
        a=find(a);
        b=find(b);
        if(a==b){
            return;
        }
        if(size[a]<size[b]){
            std::swap(a,b);
        }
        parent[b]=a;
        size[a]+=size[b];
        leftmost[a]=std::min(leftmost[a],leftmost[b]);
    }
};
struct Job{
    int deadline,id;
    long long profit;
};
int main(){
    int n;
    std::cin>>n;
    std::vector<Job>jobs(n);
    for(int i=0;i<n;++i){
        std::cin>>jobs[i].deadline>>jobs[i].profit;
        jobs[i].id=i+1;
    }
    std::sort(jobs.begin(),jobs.end(),[](Job a,Job b){
        return a.profit!=b.profit?a.profit>b.profit:a.id<b.id;
    });
    DSU free(n);
    std::vector<int>schedule(n+1);
    int count=0;
    long long profit=0;
    for(Job j:jobs){
        if(j.profit>0){
            int slot=free.leftmost[free.find(std::min(n,j.deadline))];
            if(slot==0){
                continue;
            }
            schedule[slot]=j.id;
            profit+=j.profit;
            ++count;
            free.unite(slot,slot-1);
        } // Merge the used slot with its predecessor component; zero is a sentinel.
    }
    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 plus O(n α(n+1)) amortized DSU work with path compression and union by size. O(n) jobs, schedule and DSU arrays. Compared with set predecessor queries, the selection phase becomes near-linear; sorting still dominates overall.

Example input and output

Read the same unit-job input as Job Sequencing: n≤100000, deadlines 0..10^9, profits within ±10^9. All jobs are available at zero. Print count/profit and occupied slot/job-ID pairs. Nonpositive-profit jobs are skipped.

Input

4
2 100
1 19
2 27
1 25

Output

2 127
1 3
2 1

Using slots 2 then 1 merges their availability components with the left predecessor and finally the sentinel.

Practical applications

Use DSU when choices are deleted permanently and neighboring exhausted ranges can merge. Ordered sets are simpler if deletions can be undone or choices reinserted. For graph connectivity, component metadata has a different meaning and must be redesigned.

Check your understanding

Why store leftmost separately from parent?

Put it into practice

Compare the set and DSU schedulers on the same random jobs.