Job Sequencing: When Greedy Fails and DSU Saves the Day

This One Looked Like A Classic Greedy Setup

you get a list of jobs each job has a deadline and a profit you can only do one job per time unit finish the job before or on its deadline to get the profit goal do as many high-profit jobs as you can but within their deadlines

cool

so you sort the jobs by profit descending try to place each one in the latest free slot before its deadline done right

that's exactly what i did

for job in sorted_jobs_desc:
    slot = deadline
    while slot > 0:
        if schedule[slot] is free:
            assign it
            break
        slot -= 1

this worked for a few hundred jobs maybe a few thousand

then i tested it with 10^5 jobs

boom tle

Why The Loop Is A Bottleneck

the while loop scanning for free slots is the killer

imagine a job with a deadline of 99999 and every earlier slot is filled you just did 99999 iterations for that one job and you might have to do this for 50k other jobs too you're looking at a worst-case of o(n^2)

that's when i remembered something i hadn't touched in a while disjoint set union dsu union find the thing you use in kruskal's algorithm or to track connected components the idea isn't new i saw a version of this optimization in some older cp forums dsu is old but it's fast

How Dsu Entered The Picture

• at first i blamed the input size maybe the test case was bogus
• then i saw it: the while free_spot > 0 loop was the real bottleneck
• that's linear scan per job - if deadlines are high, that loop turns into death by a thousand cuts

wait that's exactly what this job thing is

instead of looking for the nearest available free slot manually what if each slot points to the next free one

that's what find() in dsu is for

assign a job to slot 4

cool now slot 4 is used point it to slot 3

next time you call find(4) it returns 3

call find(3) if that's used it returns 2

path compression kicks in and flattens everything

you now get the next available free slot in near constant time

Final Code With Dsu

class Solution:
    def jobSequencing(self, deadline, profit):
        n = len(deadline)
        jobs = [ [i, deadline[i], profit[i]] for i in range(n) ]
        jobs.sort(key=lambda x: -x[2])

        max_deadline = max(deadline)
        parent = [i for i in range(max_deadline + 2)]

        def find(slot):
            if parent[slot] == slot:
                return slot
            parent[slot] = find(parent[slot])
            return parent[slot]

        total_jobs = total_profit = 0

        for jobid, d, p in jobs:
            available = find(d)
            if available > 0:
                parent[available] = find(available - 1)
                total_jobs += 1
                total_profit += p

        return [total_jobs, total_profit]

The Numbers

• old brute loop ~o(n * max(deadline))
• new dsu o(n * α(n)) and α(n) is practically constant
• passed every large test case instant jump from tle to ac

Final Takeaway

if a greedy algorithm starts scanning linearly too much especially in scheduling like problems dsu might be what you're looking for

nothing fancy here - just leveraging the power of efficient set operations

and some muscle memory from kruskal

References

DSU Optimization Technique

• Job Sequencing Problem using Disjoint Set - GeeksforGeeks - Explains the exact DSU optimization technique: "When we assign a time slot 't' to a job, we do union of 't' with 't-1' in a way that 't-1' becomes the parent of 't'." This is literally the same trick I stumbled into.
• Job Sequencing with Deadlines - BYJU'S - Describes the classic greedy approach: "By arranging the jobs in descending order of profit, the Greedy method can achieve an optimal sequence of jobs that maximizes the total profit while considering deadline limitations." The obvious part that worked until it didn't.

DSU Complexity & Performance

• Union By Rank and Path Compression - GeeksforGeeks - Confirms the time complexity claim: "the amortized time complexity per operation is O(α(n)), where α(n) is the inverse Ackermann function — a function that grows extremely slowly. So slowly, in fact, that α(n) < 5 for all practical input sizes." That's why I said "practically constant."
• Union-Find Comprehensive Guide - AlgoCademy - Validates the complexity analysis: "Find: O(α(n)) amortized, where α(n) is the inverse Ackermann function, which grows very slowly and is effectively constant for all practical values of n." The "near constant time" claim is backed by math.
• Disjoint-set Path Compression Analysis - LinkedIn - Confirms practical performance: "Since for all practical purposes the value of our Inverse Ackermann function is less than 4. We can say that with Path Compression implemented, the Find function can execute in a constant time." That's the real-world performance that made the difference.