# Job Sequencing Problem

Posted in  Last updated on June 9, 2022

## 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 maximised 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 is 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 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 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);
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] < arr[j + 1]:
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):
if result[j] is False:
result[j] = True
ans[j] = arr[i]
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 Job() {}
public Job(int id, int deadline, int profit)
{
this.id = id;
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>();
Console.WriteLine("Maximum profit sequence of jobs");
Job job = new Job();
job.solve(arr, 3);
}
}
```

#### Output

```Maximum profit sequence of jobs
3 1 5```