What is the question?


#1

Never understood the question even after seeing the solution.


#2

I know I am a bit late at answering this, but for better understanding I think this is the same question from geeksforgeeks. Do give it a read, if you are confused from the explanation here.

I would like to add - The gfg and the c++ editorial solution here is O(n^2) though [Although as shown in the fastest editorial c++ solution that too can be optimized to O(nlogn + Ackerman(n) + max_deadline_val) time and O(max_deadline_val), using union find algorithm for selecting available slot]. You can find details about this approach easily. So, I’ll stop explaining that.

Although I feel the best solution is O(nlogn) time and O(n) space - Using sorting in ascending order of deadlines and then using a min pq, to push the profits - However, when the number/size of pq increases the maximum deadline so far, we pop the smallest profiting job from the min pq. This approach is not documented anywhere - Disclaimer: I might be wrong, since I came up with this from the scratch - but this worked like a charm and got accepted! If this seems erroneous do let me know, I’d love to discuss and improve it in that case.