> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/greedy/job-sequencing-problem.md).

# Job Sequencing Problem

Given an array of jobs where every job has a deadline and associated profit if the job is finished before the deadline. It is also given that every job takes single unit of time, so the minimum possible deadline for any job is 1. How to maximize total profit if only one job can be scheduled at a time.

**Examples:**

```
Input: Four Jobs with following 
deadlines and profits
JobID  Deadline  Profit
  a      4        20   
  b      1        10
  c      1        40  
  d      1        30
Output: Following is maximum 
profit sequence of jobs
        c, a   


Input:  Five Jobs with following
deadlines and profits
JobID   Deadline  Profit
  a       2        100
  b       1        19
  c       2        27
  d       1        25
  e       3        15
Output: Following is maximum 
profit sequence of jobs
        c, a, e
```

```java
public class Solution {
    static class Job {
        char id; // Job Id
        int dead; // Deadline of job
        int profit; // Profit if job is over before or on deadline
    };

    public int[] printJobScheduling(Job arr[], int n) {
        Arrays.sort(arr, (a, b) -> b.profit - a.profit);

        int result[] = new int[n];
        boolean slot[] = new boolean[n];

        for (int i = 0; i < n; i++) {
            for (int j = Math.min(n, arr[i].dead) - 1; j >= 0; j--) {
                // Free slot found
                if (slot[j] == false) {
                    result[j] = i; // Add this job to result
                    slot[j] = true; // Make this slot occupied
                    break;
                }
            }
        }
        return result;
    }
}
// DSU
class Solution {
    static class Job {
        char id;
        int deadline, profit;

        public Job(char id, int deadline, int profit) {
            this.id = id;
            this.deadline = deadline;
            this.profit = profit;
        }
    }

    int parent[];

    public void printJobScheduling(ArrayList<Job> arr) {
        Collections.sort(arr, (a, b) -> b.profit - a.profit);
        // Find max deadline
        int maxDeadline = 0;
        for (Job x : arr)
            maxDeadline = Math.max(maxDeadline, x.deadline);
        // Parent array
        parent = new int[maxDeadline + 1];
        for (int i = 0; i <= n; i++)
            parent[i] = i;
        // Traverse through all the jobs
        for (Job temp : arr) {
            // Find the maximum available free slot for
            // this job (corresponding to its deadline)
            int availableSlot = dsu.find(temp.deadline);

            // If maximum available free slot is greater
            // than 0, then free slot available
            if (availableSlot > 0) {
                // This slot is taken by this job 'temp'
                // so we need to update the greatest free
                // slot. So now we need to merge parents availableSlot-1 & availableSlot
                merge(find(availableSlot - 1), availableSlot);
                System.out.print(temp.id + " ");
            }
        }
    }

    // Path Compression
    int find(int s) {
        if (s == parent[s])
            return s;
        return parent[s] = find(parent[s]);
    }

    void merge(int u, int v) {
        parent[v] = u;
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mayanktyagi3111.gitbook.io/interview-prep/greedy/job-sequencing-problem.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.