Job Sequencing Problem | Greedy Solution

The Job Sequencing Problem asks you to schedule jobs to maximize total profit, given that each job:

• Takes exactly one unit of time
• Must finish by its deadline
• Can be scheduled in any order, but at most one job can be done at a time

You need to return:

1. The number of jobs done
2. The maximum total profit

Here’s the [Problem Link] to begin with.

What does the problem say? (with examples)

You are given two arrays of equal length:

• deadline[i] is the last time slot by which job i must be completed
• profit[i] is the profit if job i is completed on or before its deadline

Each job takes one unit of time. You must schedule jobs in a time grid of slots 1, 2, ..., max_deadline so that:

• No two jobs occupy the same slot
• A job scheduled in slot t must have t <= deadline[i]
• Total profit is maximized

Example

deadline = [2, 1, 2, 1, 3]
profit   = [100, 19, 27, 25, 15]

One optimal schedule might pick three jobs within their deadlines for a total profit of 152.

Intuition and Approach (Greedy)

A classic greedy strategy is:

1. Sort jobs by profit in descending order so we try to place the most profitable jobs first
2. For each job in that order, try to place it in the latest available slot at or before its deadline
3. If such a slot is found, schedule it and add its profit; otherwise, skip the job

Why this works:

• Taking the highest-profit jobs first gives the best chance to include them
• Placing a job as late as possible preserves earlier slots for other jobs with tighter deadlines

Note: The straightforward implementation scans backward from deadline down to 1 to find a free slot. This can be slow if deadlines are large, and on some test sets this may cause TLE. It can be optimized with a Disjoint Set Union (DSU/Union-Find) structure or other data structures, but here we keep your exact code and only add comments.

Code Implementation

Your provided greedy solution, unchanged except for clarifying comments:

class Solution:
    def jobSequencing(self, deadline, profit):
        jobs = list(zip(deadline, profit))
        # Sort by profit descending
        jobs.sort(key=lambda x: x[1], reverse=True)

        # Find maximum deadline to define slot array
        max_dead = max(deadline) if deadline else 0
        slots = [-1] * (max_dead + 1)  # 1-based indexing for convenience

        total_profit = 0
        count = 0

        for d, p in jobs:
            # scan from d down to 1 for a free slot
            for slot in range(d, 0, -1):
                if slots[slot] == -1:
                    slots[slot] = 1  # mark slot filled
                    total_profit += p
                    count += 1
                    break  # move to next job

        return [count, total_profit]

Code explanation

• We pair each job as (deadline, profit) and sort by profit descending so we try the most valuable jobs first.
• We compute max_dead and build a slots array of length max_dead + 1 using 1-based indexing. Each index represents a time slot.
• For each job (d, p) in sorted order:
  • We try to place it at the latest possible free slot slot from d down to 1.
  • If we find a free slot, we occupy it and add p to total_profit.
  • If not, we skip the job.
• Finally, we return [count, total_profit].

This directly implements the greedy idea of scheduling high-profit jobs as late as possible within their deadlines.

Time and Space Complexity

Precise

• Sorting jobs by profit: O(n log n)
• For each job, scanning for a free slot takes at most min(d_i, max_dead) steps
  Total slot scans: O(Σ min(d_i, max_dead)), which in the worst case is O(n · max_dead)
• Overall time: O(n log n + n · max_dead)

Simplified

• If max_dead is proportional to n, worst-case time is O(n^2), which can cause TLE on large inputs.
• Space: slots array of size max_dead + 1 plus a list of jobs
  O(n + max_dead), simplified to O(max_dead) extra space

Note on optimization (context only, not changing your code)

• Using a Disjoint Set Union to find the nearest free slot in approximately amortized α(n) time reduces the overall to O(n log n) (for sorting) with near-constant slot-finds, which typically avoids TLE.

Conclusion

The greedy strategy of sorting by profit descending and placing each job in the latest available slot is correct and commonly taught. The provided implementation is simple and readable, but its backward slot scan can be O(n · max_deadline) and may lead to TLE on large inputs. For production or strict time limits, consider an optimized slot-finding method such as Disjoint Set Union to bring the complexity down to O(n log n) while preserving the same greedy selection logic.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.