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 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