Job Sequencing Problem

Problem

Given a set of jobs, each with its own deadline and corresponding profit. You get profit only if you complete a job before or on the deadline. Given that each work requires a single unit of time. How can overall profit be maximized if only one task may be performed at a time?

Sample Input

{ {1, 2, 100}, {2, 1, 19}, {3, 2, 27}, {4, 1, 25}, {5, 3, 15}}

Sample Output

Maximum profit sequence of jobs 
3 1 5

Approach

We can follow a greedy approach to solve the given problem. We can sort the jobs on the basis of decreasing order of profits. Then, for each job, we traverse from a given deadline to 0 and check if some slot is free. If a free slot is found, we can mark this slot as occupied. To mark slots as occupied, we can use a set or an array. This approach takes O(NlogN) time and O(N) space.

For the above sample input, here are the time slots at which we do the jobs. Job 3 ? 1 (got profit of 27)Job 1 ? 2 (got profit of 100)Job 5 ? 3 (got profit of 15)

C++

#include<iostream>
#include<algorithm>
using namespace std;
struct Job
{
int id; // Job Id
int deadline; // Deadline of job
int profit; // Profit of job
};
bool comparison(Job a, Job b)
{
return (a.profit > b.profit);
}
void solve(Job arr[], int n)
{
// Sort all jobs according to decreasing order of prfit
sort(arr, arr+n, comparison);
int result[n];
bool slot[n];
for (int i=0; i<n; i++)
slot[i] = false;
for (int i=0; i<n; i++) { for (int j=min(n, arr[i].deadline)-1; j>=0; j--)
{
// Free slot found
if (slot[j]==false)
{
result[j] = i;
slot[j] = true;
break;
}
}
}
for (int i=0; i<n; i++)
if (slot[i])
cout << arr[result[i]].id << " ";
}
int main()
{
Job arr[] = { {1, 2, 100}, {2, 1, 19}, {3, 2, 27},
{4, 1, 25}, {5, 3, 15}};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Maximum profit sequence of jobs \n";
solve(arr, n);
return 0;
}

Output

Maximum profit sequence of jobs 
3 1 5

Python

def solve(arr, t):
 n = len(arr)
 for i in range(n):
 for j in range(n - 1 - i):
 if arr[j][2] < arr[j + 1][2]:
 arr[j], arr[j + 1] = arr[j + 1], arr[j]
 result = [False] * t
 ans = ['-1'] * t
 for i in range(len(arr)):
 for j in range(min(t - 1, arr[i][1] - 1), -1, -1):
 if result[j] is False:
 result[j] = True
 ans[j] = arr[i][0]
 break
 print(ans)
arr = [[1, 2, 100],
 [2, 1, 19],
 [3, 2, 27],
 [4, 1, 25],
 [5, 3, 15]]
print("Maximum profit sequence of jobs")
solve(arr, 3)

Output

Maximum profit sequence of jobs
[3, 1, 5]

C#

using System;
using System.Collections.Generic;
class Solutions : IComparer<Job>
{
public int Compare(Job x, Job y)
{
if (x.profit == 0 || y.profit== 0)
{
return 0;
}
return (y.profit).CompareTo(x.profit);
}
}
public class Job{
public int deadline, profit, id;
public Job() {}
public Job(int id, int deadline, int profit)
{
this.id = id;
this.deadline = deadline;
this.profit = profit;
}
void solve(List<Job> arr, int t)
{
// Length of array
int n = arr.Count;
Solutions solution = new Solutions();
arr.Sort(solution);
bool[] result = new bool[t];
int[] job = new int[t];
for (int i = 0; i < n; i++)
 {
 for (int j = Math.Min(t - 1, arr[i].deadline - 1); j >= 0; j--)
 {
if (result[j] == false)
{
result[j] = true;
job[j] = arr[i].id;
break;
}
}
}
foreach (int itr in job)
{
Console.Write(itr + " ");
}
Console.WriteLine();
}
static public void Main ()
{
List<Job> arr = new List<Job>();
arr.Add(new Job(1, 2, 100));
arr.Add(new Job(2, 1, 19));
arr.Add(new Job(3, 2, 27));
arr.Add(new Job(4, 1, 25));
arr.Add(new Job(5, 3, 15));
Console.WriteLine("Maximum profit sequence of jobs");
Job job = new Job();
job.solve(arr, 3);
}
}

Output

Maximum profit sequence of jobs 
3 1 5

People are also reading:

• Find Maximum Subarray Sum
• Subarray with Sum k
• Longest Palindromic Subsequence
• Move all zeros present in an array to the end
• Find LCM and HCF of two numbers
• Print a Man using Graphics
• Construct a tree from Inorder and Level order traversals
• Sort binary array in linear time
• Maximum of all Subarrays of size K
• Rod Cutting Problem – Dynamic Programming