Microsoft | Phone Screen | Job Sequencing Problem
psavnani
1083
GreedyInterview

Question:
Given a set of N jobs where each jobi has a deadline and profit associated with it.
Each job takes 1 unit of time to complete and only one job can be scheduled at a time. We earn the profit associated with job if and only if the job is completed by its deadline.
Find the number of jobs done and the maximum profit.

Note: Jobs will be given in the form (Jobid, Deadline, Profit) associated with that Job.

Example1:

Input:
N = 4
Jobs = {(1,4,20),(2,1,10),(3,1,40),(4,1,30)}
Output:
2 60
Explanation:
Job1 and Job3 can be done with
maximum profit of 60 (20+40).

Example2:

Input:
N = 5
Jobs = {(1,2,100),(2,1,19),(3,2,27),
        (4,1,25),(5,1,15)}
Output:
2 127
Explanation:
2 jobs can be done with
maximum profit of 127 (100+27).

Solution:

/*
struct Job 
{ 
    int id;	 // Job Id 
    int dead; // Deadline of job 
    int profit; // Profit if job is over before or on deadline 
};
*/
class Solution 
{
    public:
    //Function to find the maximum profit and the number of jobs done.
    static bool comp(const Job& job1, const Job& job2){
        return job1.profit > job2.profit;
    }
    
    vector<int> JobScheduling(Job arr[], int n) { 
        // your code here
        int max_deadline = arr[0].dead;
        for(int i=1; i<n; i++)
            max_deadline = max(max_deadline, arr[i].dead);
            
        vector<int> sequence(max_deadline+1, -1);
        sort(arr, arr+n, comp);
        
        int countJobs=0;
        int maxProfit=0;
        
        for(int i=0; i<n; i++) {
            for(int j=arr[i].dead; j>0; j--) {
                if(sequence[j]==-1) {
                    sequence[j]=i;
                    countJobs++;
                    maxProfit+=arr[i].profit;
                    break;
                }
            }
        }
        return {countJobs, maxProfit};
    } 
};
Comments (4)