Greedy: Job Scheduling with Deadlines

Maximizing profit from a set of jobs is a classic optimization problem with real-world parallels in manufacturing, computing, and project management. When each job has a fixed deadline and profit, you cannot simply execute them all; you need a strategy to select and order them. The greedy approach provides an elegant and provably optimal solution by strategically scheduling the most valuable jobs as late as possible, ensuring no deadlines are missed and total profit is maximized.

Understanding the Problem and Greedy Intuition

The Job Scheduling with Deadlines problem is formally defined as follows: you are given $n$ jobs. Each job $i$ has:

1. A deadline $d_i$ (a positive integer representing the latest time slot by which the job must be completed).
2. A profit $p_i$ (a positive integer earned if the job is completed on or before its deadline).

Time is divided into discrete slots, starting from slot 1. Each job requires a single, indivisible time slot to complete. If a job is scheduled in a slot $t$, it must hold that $t\le d_i$. The goal is to find a feasible schedule—a subset of jobs assigned to distinct time slots—that maximizes the sum of profits.

The greedy intuition is straightforward: to maximize profit, prioritize jobs with the highest profit. However, simply picking the highest-profit jobs in descending order fails if you don't consider deadlines. A very high-profit job with an imminent deadline must be scheduled early, potentially blocking later slots. The optimal strategy refines this: always select the highest-profit job that can still be fitted into its latest possible free slot before its deadline. This "as-late-as-possible" placement preserves earlier slots for other jobs that might have tighter deadlines.

The Greedy Algorithm: Step-by-Step

The algorithm proceeds in three clear stages:

1. Sorting: Sort all jobs in non-increasing order of profit. This ensures we always consider the most profitable available job first.
2. Slot Assignment: Initialize an array to track the availability of time slots, up to the maximum deadline $m=\max (d_i)$. For each job in the sorted list:

• Find the latest free slot $t$ that is less than or equal to the job's deadline $d_i$.
• If such a free slot exists, assign the job to that slot, mark the slot as occupied, and add the job's profit to the total.
• If no free slot exists before the deadline, discard the job (it cannot be scheduled).

1. Output: The sequence of assigned jobs (or their profits) constitutes the optimal schedule.

A naive implementation of Step 2 would, for each job, linearly scan slots from its deadline backward to find a free one. This leads to a complexity of $O(n^2)$ if all deadlines are of order $n$. The key to an efficient $O(n\log n)$ implementation is optimizing this "find latest free slot" operation.

Optimizing with Disjoint Set Union (DSU)

The disjoint set union (DSU) data structure, also known as Union-Find, is perfectly suited to make the slot-finding process nearly constant time. Here’s how it adapts to this problem:

• Representation: We create a DSU where each time slot is an element. Slot $t$ is initially its own parent.
• Objective: For a given job with deadline $d$, we need to find the latest free slot $\le d$. In DSU terms, we want the root (or representative) of the set containing deadline $d$.
• Operation: The find(x) operation returns the greatest available slot $\le x$. Initially, find(d) returns $d$ itself, indicating slot $d$ is free.
• Scheduling: When we schedule a job in slot $t$, we "consume" that slot. To reflect this, we union slot $t$ with slot $t-1$. This means subsequent find calls for any deadline that maps to $t$ will now return $t-1$, the next latest available slot.
• Signaling Unavailability: If find(d) returns 0, it means no free slot exists for that job before its deadline.

This optimization reduces the per-job slot-finding cost to $O(\alpha (n))$, where $\alpha$ is the inverse Ackermann function, effectively constant. Thus, the overall complexity is dominated by the initial sorting: $O(n\log n)$.

Proof of Optimality

Why is this greedy choice optimal? The proof uses an exchange argument, a standard technique for greedy algorithms.

1. Assume our greedy algorithm produces schedule $G$, and let $O$ be an optimal schedule. If $G$ is not optimal, then $O$ has a higher total profit.
2. Consider the jobs in order of descending profit. Let job $i$ be the first job (highest profit) that is in $G$ or $O$ but not in both.
3. Case Analysis:

• If job $i$ is in $O$ but not in $G$, it's because when the greedy algorithm considered $i$, all slots $\le d_i$ were already occupied by jobs with profit $\ge p_i$ (since we process in profit order). We can swap $i$ into $O$ in place of one of these jobs (which has equal or lower profit), not decreasing $O$'s profit.
• If job $i$ is in $G$ but not in $O$, then $O$ must contain some other job $j$ in the slot where $G$ placed $i$. Since $i$ is the first point of difference and has higher profit than any unscheduled job at that point, $p_i\ge p_j$. Replacing $j$ with $i$ in $O$ does not decrease profit and makes $O$ more similar to $G$.

1. By repeatedly applying this exchange, we can transform $O$ into $G$ without ever decreasing its total profit. Therefore, the profit of $G$ must be at least that of $O$, proving $G$ is optimal.

Common Pitfalls

1. Sorting by Deadline or Ratio: A common mistake is to sort jobs by deadline (earliest deadline first) or by profit-to-deadline ratio. These strategies are not optimal for maximizing profit. For example, two jobs with profits (100, deadline 1) and (99, deadline 100) are best scheduled by taking the highest profit first, even though its deadline is immediate. Always sort by profit descending.

1. Incorrect Slot Indexing (Off-by-One Errors): Time slots are often 1-indexed (slot 1, slot 2, ...). When using DSU, ensure your parent initialization and "unavailable" signal (usually slot 0) are handled correctly. Attempting to access a non-existent slot 0 or mis-mapping deadlines to slots is a frequent implementation bug.

1. Assuming Greedy is Obvious Without Proof: While the algorithm seems intuitive, skipping the exchange argument proof is a conceptual pitfall. Understanding why the "latest possible slot" rule is crucial and why the algorithm works for all inputs solidifies your grasp of greedy strategy, which is essential for adapting it to more complex problems.

1. Using Inefficient Slot Finding: Implementing the slot scan with a linear search is acceptable for small inputs but fails on larger scales. Recognizing that this is a "union-find" problem—finding the greatest available predecessor—is key to an efficient solution. Not leveraging DSU misses the opportunity for the optimal $O(n\log n)$ runtime.

Summary

• The Greedy Algorithm for Job Scheduling with Deadlines maximizes total profit by always selecting the highest-profit job and placing it in the latest available time slot before its deadline.
• Sorting all jobs in non-increasing order of profit is the foundational first step.
• The Disjoint Set Union (DSU) data structure optimizes the search for the latest free slot, reducing the algorithm's complexity to $O(n\log n)$, dominated by the sort.
• The optimality of the greedy approach can be rigorously proven using an exchange argument, demonstrating that no other schedule can yield a higher total profit.
• Critical implementation details include careful 1-based slot indexing and understanding why sorting by profit, not deadline, is the correct strategy.