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