Job Sequencing Problem | Problem of the Day | GeeksForGeeks

[@mathematics3398]

Table of Contents
0:00 Problem Statement
1:46 Solution
6:41 Pseudo Code
9:42 Code - Python
10:34 Code - C++

[@mathematics3398]

class Solution
{
public:
vector JobScheduling(Job arr[], int n)
{
vector used(n + 1, false);
int profit = 0, num_jobs = 0;
vector ans;
sort(arr, arr + n, [](const Job &first, const Job &second) { return first.profit > second.profit; });
for (int i = 0; i < n; i++) {
int deadline = arr[i].dead;
while (deadline > 0) {
if (not used[deadline]) {
used[deadline] = true;
profit += arr[i].profit;
num_jobs++;
break;
}
deadline--;
}
}
ans.push_back(num_jobs);
ans.push_back(profit);
return ans;
}
};

[@mathematics3398]

class Solution:
#Function to find the maximum profit and the number of jobs done.
def JobScheduling(self,Jobs,n):
Jobs.sort(key=lambda x:x.profit, reverse=True)
used = [False for _ in range(n + 1)]
profit = 0
num_jobs = 0
for j in Jobs:
deadline = j.deadline
while deadline > 0:
if not used[deadline]:
used[deadline] = True
profit += j.profit
num_jobs += 1
break
deadline -= 1
return [num_jobs, profit]