I solved these two questions but had problem.
In COCOPROD I used recursion+memoization but One Test case didn’t passed
My Code : COCOPROD
In CHEFSTCK I reduced it to Trivial Job Scheduling Greedy Problem but Two Test cases didn’t passed
My Code : CHEFSTCK
*If Someone could either rectify my approach or check my code for a minute bug, It would be real helpful.
Thanks*
1 Like
Doesn’t the job scheduling give the max number of jobs you can do and not the minimum time you remain free? I don’t think we can reduce it to the standard job scheduling problem.
P.S. : my profit[i] will be finish[i] - start[i] i.e. the length of the spanning stick.
Check My Code Attached Above
length of max no. of jobs is different from maximum time doing the job… for example if i have a segment 1-10 and have sticks from 1-2, 3-4, 5-6, 3-10… your answer would be 4 as u will pick first three sticks but the answer should be 1 by placing 1st and last stick
1 Like
@mohitkurani98 That’s exactly what I was pointing out.
@mohitkurani98 first of all the answer would be 2. and My code will give 2 as expected. see @ista2000
0-1 and 2-3 will give me count=2
reference: https://www.ideone.com/pNIIcE
Are you really taking max number of jobs and subtracting it from m? If yes then in this case
1
3 15
3 5
8 10
1 15
Your code returns 1 but it shouldn’t if it is doing what you say it is doing.
may be I was not able to convey what I am doing?
for(int i=0;i<n;i++)
{
cin>>arr[i].start>>arr[i].finish;
arr[i].profit = arr[i].finish - arr[i].start;
}
ll ans = m-findMaxProfit(arr,n);
here findMaxProfit is the basic weighted job scheduling algorithm as mentioned.
1 Like
for(int i=0;i<n;i++) {
cin>>arr[i].start>>arr[i].finish;
arr[i].profit = arr[i].finish - arr[i].start;
}
ll ans = m-findMaxProfit(arr,n);
here findMaxProfit is the basic weighted job scheduling algorithm as mentioned.
1 Like