Last Updated on March 30, 2022 by Ria Pathak
CONCEPTS USED:
Greedy algorithm.
DIFFICULTY LEVEL:
Hard
PROBLEM STATEMENT(SIMPLIFIED):
One day Aman went to the office and his boss gave him some tasks to finish within the given deadline and told him to earn maximum profit. Boss gave him a set of N task where each taski has a deadline and profit associated with it. Each task takes 1 unit of time to complete and only one job can be scheduled at a time. Aman can earn the profit if and only if the job is completed by its deadline. Aman has to find the maximum profit but he doesn’t know how to maximize profit so he asks for your help.
See original problem statement here
For Example :
7
1 1 3
2 3 5
3 4 20
4 3 18
5 2 0
6 1 6
7 2 30
74
The first task completed will be task-6 with a profit of 6.
The second task completed will be task-7 with a profit of 30.
The third task completed will be task-4 with a profit of 18.
The last task completed will be task-3 with a profit of 20.
So maximum profit = 6+30+18+20=74.OBSERVATION:
Input: Five Jobs with following
deadlines and profits
ID Deadline Profit
x 2 100
y 1 19
z 2 27
u 1 25
v 3 15
Output: Following is maximum
profit sequence of jobs
z,x,v
To solve this problem, the given jobs are sorted according to their profit in a descending order.
From the given jobs, first we select x, as it can be completed within its deadline and gives maximum profit.
Next, z is selected as it gives more profit compared to y.
y cannot be selected as its deadline is over.
The job u is discarded as it cannot be executed within its deadline.
v is selected as it can be completed within its deadline.
Thus, the solution is the sequence of jobs (z,x,v), which are being completed within their deadline and give maximum profit.
Total profit 100+ 27+15 =142.SOLVING APPROACH:
This question is the famous job sequencing problem which uses greedy approach .
Since our objective is to select jobs that will give us higher profit,to solve this problem, the given jobs are sorted according to their profit in a descending order.
We adopt a greedy algorithm to determine how the next job is selected for an optimal solution. The greedy algorithm described below always gives an optimal solution to the job sequencing problem.
Sort all the given jobs in the decreasing order of their profits.
Iterate on jobs in decreasing order of profit.For each job , do the following :
Find a time slot i, such that slot is empty and i >>
If no such i exists, then ignore the job.
SOLUTIONS:
#include <stdio.h>
#define MAX 1002
typedef struct Job {
int id;
int deadline;
int profit;
} Job;
void jobSequencingWithDeadline(Job jobs[], int n);
int minValue(int x, int y) {
if(x < y) return x;
return y;
}
int main(void) {
int n;scanf("%d",&n);
Job jobs[n];
for(int i=0;i<n;i++)
{
scanf("%d%d%d",&jobs[i].id,&jobs[i].deadline,&jobs[i].profit);
}
Job temp;
int i,j;
for(i = 1; i < n; i++) {
for(j = 0; j < n - i; j++) {
if(jobs[j+1].profit > jobs[j].profit) {
temp = jobs[j+1];
jobs[j+1] = jobs[j];
jobs[j] = temp;
}
}
}
jobSequencingWithDeadline(jobs, n);
return 0;
}
void jobSequencingWithDeadline(Job jobs[], int n) {
int i, j, k, maxprofit;
int timeslot[n];
int filledTimeSlot = 0;
int dmax = 0;
for(i = 0; i < n; i++) {
if(jobs[i].deadline > dmax) {
dmax = jobs[i].deadline;
}
}
for(i = 1; i <= dmax; i++) {
timeslot[i] = -1;
}
for(i = 1; i <= n; i++) {
k = minValue(dmax, jobs[i - 1].deadline);
while(k >= 1) {
if(timeslot[k] == -1) {
timeslot[k] = i-1;
filledTimeSlot++;
break;
}
k--;
}
if(filledTimeSlot == dmax) {
break;
}
}
maxprofit = 0;
for(i = 1; i <= dmax; i++) {
maxprofit += jobs[timeslot[i]].profit;
}
printf("%d\n", maxprofit);
}
#include<iostream>
#include<algorithm>
using namespace std;
struct Job
{
int id; // Job Id
int dead; // Deadline of job
int profit; // Profit if job is over before or on deadline
};
bool comparison(Job a, Job b)
{
return (a.profit > b.profit);
}
int printJobScheduling(Job arr[], int n)
{
sort(arr, arr+n, comparison);
int result[n]; // To store result (Sequence of jobs)
bool slot[n]; // To keep track of free time slots
int maxpro=0;
// Initialize all slots to be free
for (int i=0; i<n; i++)
slot[i] = false;
// Iterate through all given jobs
for (int i=0; i<n; i++)
{
// Find a free slot for this job (Note that we start
// from the last possible slot)
for (int j=min(n, arr[i].dead)-1; j>=0; j--)
{
// Free slot found
if (slot[j]==false)
{
result[j] = i; // Add this job to result
slot[j] = true; // Make this slot occupied
maxpro+=arr[i].profit;
break;
}
}
}
return maxpro;
// Print the result
// for (int i=0; i<n; i++)
// if (slot[i])
// cout << arr[result[i]].id << " ";
}
int main()
{
int n;
cin>>n;
Job arr[n];
for(int i=0;i<n;i++)
cin>>arr[i].id>>arr[i].dead>>arr[i].profit;
cout <<printJobScheduling(arr, n);
return 0;
}
import java.util.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
class JobSequencingProblem {
static class Job implements Comparable<Job> {
int id;
int deadline;
int profit;
@Override
public int compareTo(Job otherJob) {
return otherJob.profit - this.profit;
}
public Job(int id, int deadline, int profit) {
this.id = id;
this.deadline = deadline;
this.profit = profit;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
JobSequencingProblem jobSequencing = new JobSequencingProblem();
ArrayList<Job> jobs = new ArrayList<Job>();
for(int i=0;i<n;i++)
{
int id = sc.nextInt();
int dead = sc.nextInt();
int pro = sc.nextInt();
jobs.add(new Job(id, dead, pro));
}
Collections.sort(jobs);
jobSequencing.printJobSequence(jobs, jobs.size());
}
private void printJobSequence(ArrayList<Job> jobs, int size) {
Boolean[] slots = new Boolean[size];
Arrays.fill(slots, false);
int result[] = new int[size];
for (int i = 0; i < size; i++) {
for (int j = jobs.get(i).deadline - 1; j >= 0; j--) {
if (!slots[j]) {
result[j] = i;
slots[j] = true;
break;
}
}
}
int ans=0;
for (int i = 0; i < jobs.size(); i++) {
if (slots[i])
ans+=jobs.get(result[i]).profit;
}
System.out.println(ans);
}
}
[forminator_quiz id="1419"]
This article tried to discuss the concept of Greedy algorithm. Hope this blog helps you understand and solve the problem. To practice more problems on Greedy algorithm you can check out MYCODE | Competitive Programming.