// { Driver Code Starts
// Program to find the maximum profit job sequence from a given array
// of jobs with deadlines and profits
#include<bits/stdc++.h>
using namespace std;
// A structure to represent a job
struct Job
{
int id; // Job Id
int dead; // Deadline of job
int profit; // Profit if job is over before or on deadline
};
// } Driver Code Ends
/*
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.
vector<int> JobScheduling(Job arr[], int n)
{
// your code here
vector<vector<int>> m(n);
for(int i=0;i<n;i++)
{
if(m[arr[i].dead].size())
{
m[arr[i].dead][0]=max(m[arr[i].dead][0],arr[i].profit);
}
m[arr[i].dead].push_back(arr[i].profit);
}
int task=0;
int profit=0;
for(auto x: m)
{
if(x[0])
{
task+=1;
profit+=x[0];
}
}
return {task,profit};
}
};
// { Driver Code Starts.
// Driver program to test methods
int main()
{
int t;
//testcases
cin >> t;
while(t--){
int n;
//size of array
cin >> n;
Job arr[n];
//adding id, deadline, profit
for(int i = 0;i<n;i++){
int x, y, z;
cin >> x >> y >> z;
arr[i].id = x;
arr[i].dead = y;
arr[i].profit = z;
}
Solution ob;
//function call
vector<int> ans = ob.JobScheduling(arr, n);
cout<<ans[0]<<" "<<ans[1]<<endl;
}
return 0;
}
// } Driver Code Ends
Wait
> Job arr[n]
Why not allocate as much as you need ?
\Device\NUL
klimi
Ольга
Michel
Pavel
Nobody🪲
Captain
Αλι