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
Leave a Comment on this Post