Job Sequencing Problem

Problem Statement

Given jobs with deadlines and profits, schedule jobs such that profit is maximized and only one job can be done at a time.

---

Brute Force Intuition

Try every possible ordering of jobs and calculate the profit for valid schedules.

Since all permutations must be explored, the solution becomes infeasible for large inputs.

Complexity

• Time Complexity: O(N!)
• Space Complexity: O(N)

---

Moving Towards the Optimal Approach

A job with higher profit should be given priority.

To maximize total profit:

1. Sort jobs by profit descending.
2. Place each job in the latest available slot before its deadline.

This keeps earlier slots free for other jobs.

---

Greedy Pattern Recognition

Whenever you see:

• Profit maximization
• Deadlines
• One task per slot

Think:

Sort by Profit Descending

---

Optimal Java Solution

import java.util.*;

class Solution {

    int[] JobScheduling(Job arr[], int n) {

        Arrays.sort(arr, (a, b) -> b.profit - a.profit);

        int maxDeadline = 0;

        for (Job job : arr) {
            maxDeadline = Math.max(maxDeadline, job.deadline);
        }

        int[] slots = new int[maxDeadline + 1];

        Arrays.fill(slots, -1);

        int jobsDone = 0;
        int totalProfit = 0;

        for (Job job : arr) {

            for (int j = job.deadline; j > 0; j--) {

                if (slots[j] == -1) {
                    slots[j] = job.id;
                    jobsDone++;
                    totalProfit += job.profit;
                    break;
                }
            }
        }

        return new int[]{jobsDone, totalProfit};
    }
}

---

Dry Run

Job  Deadline Profit

A      2       100
B      1       19
C      2       27
D      1       25
E      3       15

After profit sorting:

A(100), C(27), D(25), B(19), E(15)

Schedule:

Slot 2 -> A
Slot 1 -> C
Slot 3 -> E

Result

Jobs Done = 3
Profit = 142

---

Complexity Analysis

Metric	Complexity
Time	O(N × MaxDeadline)
Space	O(MaxDeadline)

---

Interview One-Liner

Sort jobs by profit and schedule each job in the latest available slot before its deadline.