# Arnhav’s Cake Problem (Hard Version) Editorial

Arnhav's Cake Problem (Hard Version) Editorial

Abstract:
It was the harder version of the problem ACPE in the same contest. It again involves the use of greedy algorithm to maximise profit. But the constraints are higher this time and the O(n.k) solution for ACPE will produce TLE. Here we make use of priority queue to select jobs of highest profit from last day onwards.

Brief Solution:
For each day, list the jobs whose deadline is on that day.
Create a priority queue Q and starting from last day, add all jobs listed on that day to Q.
For each day, until more jobs can be done on that day or Q becomes empty, add the profit of the top job to total profit and remove top element of Q.
Then move onto the previous day and continue till day one.

MAX-PROFIT(jobs,days)
1. for i from 1 to jobs.size
3. priority_queue Q
4. for i from days.size till 1
5. for j from 1 to days[i].job_list.size()
6. Q.add(days[i].job_list[j])	// add all the jobs on day i to  Q

7. for i from 1 to days[i].job_num
8. if(Q is not empty)

9.   total+=Q.front.profit

10.  Q.remove(Q.front)

11. else break