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 refer the data structures in java and 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.

>1. Sort all the given jobs in the decreasing order of their profits.
>
>2. Iterate on jobs in decreasing order of profit.For each job , do the following :
>>>a. Find a time slot i, such that slot is empty and i >>
>>>b. 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);
    }
    }

Previous post FRACTION
Next post KABADDI MODIFIED

Leave a Reply

Your email address will not be published. Required fields are marked *