Job Sequencing Problem

Problem Description

In this problem, we are given a set of n jobs. Each job has the following parameters:

1. ID: Unique identifier for the job.
2. Deadline: The time by which the job must be completed.
3. Profit: The profit associated with completing the job.

Goal

Determine the optimal sequence of jobs that maximizes the profit while ensuring that no two jobs are executed simultaneously and each job is completed within its deadline.

---

Steps to Solve the Problem

1. Sort Jobs by Profit (Descending Order):

Sort the jobs in descending order based on their profits. This ensures that the most profitable jobs are considered first.

---

2. Find the Maximum Deadline:

Find the maximum deadline among all jobs. This determines the number of time slots available.

---

3. Initialize Variables:

• slots: An array of size maxDeadline initialized with -1. This array tracks which job is assigned to each time slot.
• maxProfit: Initialize to 0 to track the maximum profit achieved.
• count: Initialize to 0 to count the number of jobs included in the optimal sequence.

---

4. Iterate Over Jobs:

For each job in the sorted list:

• Check if there is an available time slot before the job's deadline.
• If an available slot is found:
  • Assign the job to that slot.
  • Increment the job count.
  • Add the job's profit to maxProfit.

---

5. Return Results:

After iterating through all jobs, return:

• count: Total number of jobs included in the sequence.
• maxProfit: Maximum profit achieved.

---

Example

Input:

jobs = [ {id: 1, deadline: 2, profit: 100}, {id: 2, deadline: 1, profit: 19}, {id: 3, deadline: 2, profit: 27}, {id: 4, deadline: 1, profit: 25}, {id: 5, deadline: 3, profit: 15} ]

Steps:

1. Sort Jobs by Profit:
   Sorted jobs:
   [ {id: 1, profit: 100}, {id: 4, profit: 25}, {id: 3, profit: 27}, {id: 2, profit: 19}, {id: 5, profit: 15} ]
2. Maximum Deadline:
   Maximum deadline = 3
3. Assign Jobs to Slots:
   • Job 1: Assigned to slot 2.
   • Job 3: Assigned to slot 1.
   • Job 5: Assigned to slot 3.

Output:

count = 3 (Jobs 1, 3, and 5)
maxProfit = 142

---

Test Cases

Test Case 1

Input:
jobs = [ {id: 1, deadline: 2, profit: 50}, {id: 2, deadline: 1, profit: 40}, {id: 3, deadline: 2, profit: 60}, {id: 4, deadline: 1, profit: 20} ]

Output:
count = 2 (Jobs 3 and 1)
maxProfit = 110

---

Test Case 2

Input:
jobs = [ {id: 1, deadline: 1, profit: 10}, {id: 2, deadline: 2, profit: 20}, {id: 3, deadline: 3, profit: 30} ]

Output:
count = 3 (Jobs 3, 2, and 1)
maxProfit = 60

---

Test Case 3

Input:
jobs = [ {id: 1, deadline: 3, profit: 20}, {id: 2, deadline: 3, profit: 15}, {id: 3, deadline: 1, profit: 10} ]

Output:
count = 2 (Jobs 1 and 3)
maxProfit = 30

---

Constraints

1. 1 <= n <= 1000
2. 1 <= profit[i], deadline[i] <= 10^4

---

Complexity

Time Complexity:

• Sorting: O(n log n)
• Assigning Jobs to Slots: O(n * d) (where d is the maximum deadline)

Space Complexity:

• O(d) for the slots array.

— Written by Saurabh Patil • B.Tech CSE • Software Developer