Arnhav’s Cake Problem (Hard Version) Editorial

editorial
,
1

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
    2. 

  2. days[jobs[i].deadline].job_list.add(jobs[i])	//add the job to the list in its deadline
    3. 

  3. priority_queue Q
    4. 

  4. for i from days.size till 1
    5. 

  5. for j from 1 to days[i].job_list.size()
    6. 

  6. 

    Q.add(days[i].job_list[j])	// add all the jobs on day i to  Q

    

    7. 

  7. for i from 1 to days[i].job_num
    8. 

  8. 

    if(Q is not empty)

    

    9. 

  9. 

      total+=Q.front.profit

    

    10. 

  10. 

     Q.remove(Q.front)

    

    11. 

  11. else break
    
12.return total
    

    12.

Time-Complexity:

  1. Line 1 and 2 - creating list for every day: O(k)
  2. Adding one job to Q: O(log k)
  3. Adding every job to Q: O(k log k)
  4. Line 5 and 6 - checking for everyday and adding every job to Q: O(n + klogk)
  5. Removing one job from Q - O(log k)
  6. Line 7 to 11 - checking for everyday and removing every job from Q: O(n + klogk)

Overall: O(n + klogk)