C++ Job Sequencing with deadline (Greedy approach)














































C++ Job Sequencing with deadline (Greedy approach)



JOB SEQUENCING WITH Deadline

Job sequencing is of the classic problems that can be solved using greedy algorithm.

Here we are given an array of jobs having a specific deadline associated with a profit, if the job is done within the deadline.

Our task is to assign jobs in a schedule such that, only one job is done at a time and profit is maximized.

OUR WAY OF APPROACH


  • We have to sort the jobs in descending order of profit.
  • Next, we have to iterate through the job and select slots.
  • Slot i is selected if,       
             a. Slot i is not previously selected.
	      b. i < deadline
	      c. i should be just less than the deadline if possible (so that other slots can be optimized).
  • If no such slot is possible, ignore the job.

EXAMPLE


Input:

JobID  Deadline   Profit
  1           2          20   
  2           2          15
  3           1          10  
  4           3           5
  5	        3           1
  

Output:

Job sequenced in order: 2 1 4

Explanation:


Here the maximum deadline is 3. Maximum profit is given by Job1. And since it has deadline 2 it occupies position2 in the job sequence. Next maximum profit is given by Job2. Since position 2 is occupied by Job1, it occupies the next position to the front of 2 ie. position1. We do not take Job3 into consideration because, it has deadline 1 and position 1 is already filled with a better job. Next, Job4 is taken and placed in position3, since it has maximum profit compared to Job5.

CODE:

#include <bits/stdc++.h>
using namespace std;

//structure for holding values
typedef struct Job
{
    int jobNum;
    int deadline;
    int profit;
}Job;

bool compare(Job a, Job b);
void jobSequencing(Job input[], int num);

int main()
{
    int num;
    cin >> num;
    Job input[num];
    // inputing the values
    for (int i = 0; i < num; i++)
    {
        cin >> input[i].jobNum;
        cin >> input[i].deadline;
        cin >> input[i].profit;
    }

    jobSequencing(input, num);
}

// a custom comparison function for arrenging jobs in decreasing order of profit
bool compare(Job a, Job b)
{
    return (a.profit > b.profit);
}

// main part of code where job sequencing happens
void jobSequencing(Job input[], int num)
{
    sort(input, input + num, compare);

    int result[num];
    
    bool slot[num];
    // setting all values in slot as false
    memset(slot, 0, sizeof(slot));

    for (int i = 0; i < num; i++)
    {
        for (int j = min(num, input[i].deadline)-1; j >= 0; j--)
        {
            if(slot[j] == false)
            {
                result[j] = i;
                slot[j] = true;
                break;
            }
        }
    }

    cout << "Job sequenced in order: ";
    for (int i=0; i<num; i++)
    {
       if (slot[i] == true)
        cout << input[result[i]].jobNum << " ";
    }
}

More Articles of Praveen Lal T H:

Name Views Likes
C++ : Find HCD and LCM in one line code 2441 0
C++ Counting occurrences using MAP (STL) 7033 0
C++ Splitting a sentence into words and putting into a container 1675 0
C++ Job Sequencing with deadline (Greedy approach) 4396 0
C++ std::wcin 950 0
C++ std::wcout 1292 1
C++ memset() 313 0
C++ CHECK NUMBER IS ODD OR EVEN USING NOR 212 0
Make C++ run faster 355 1

Comments