-
Notifications
You must be signed in to change notification settings - Fork 9
/
Job Sequencing.cpp
43 lines (33 loc) · 1.21 KB
/
Job Sequencing.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// PROBLEM :- https://practice.geeksforgeeks.org/problems/job-sequencing-problem-1587115620/1#
// GFG | MEDIUM | GREEDY, HEAP, DISJOINT SET
// Solution 1:- T.C. O(N * DAYS) S.C O(N)
// Sort through the jobs in decending order of their profit.
// Choose ith job, and place it at the first unused day from DAY deadline until DAY 1.
class Solution
{
public:
vector<int> JobScheduling(Job arr[], int n)
{
sort(arr, arr + n, [](Job &j1, Job &j2){
return j1.profit > j2.profit;
});
vector<bool> daysUsed(101, false);
int ansProfit = 0;
int jobsUsed = 0;
for(int i = 0 ; i < n ; i++){
int deadline = arr[i].dead;
int profit = arr[i].profit;
for(int j = deadline ; j >= 1 ; j--){
if(daysUsed[j] == false){
daysUsed[j] = true;
ansProfit += profit;
jobsUsed++;
break;
}
}
}
return {jobsUsed, ansProfit};
}
};
// Solution 2 :- Using Disjoing Set. T.C. O(NlogN) S.C O(N)
// https://www.cdn.geeksforgeeks.org/job-sequencing-using-disjoint-set-union/