Maximize Points After Choosing K Tasks - Solution & Explanation

Problem Overview: You are given a list of tasks where each task has a requirement and a reward (points). You can complete at most k tasks, and a task becomes available only when your current points meet its requirement. The goal is to pick tasks in an order that maximizes the total points after completing up to k tasks.

Approach 1: Brute Force / Backtracking (Exponential Time)

Try every possible sequence of up to k tasks. At each step, iterate through all remaining tasks and pick one whose requirement is less than or equal to the current points. Recursively continue while tracking the best score. This approach quickly becomes infeasible because the number of permutations grows factorially. Time complexity is O(n!) in the worst case with O(n) recursion space.

Approach 2: Greedy + Sorting + Max Heap (Optimal) (O(n log n))

Sort tasks by their requirement so you can efficiently identify which tasks become available as your points increase. Iterate up to k times and push the reward of every task whose requirement is <= current points into a max heap. The heap always keeps the highest reward available at the top. Each round, pop the maximum reward task and add its points to your total. This greedy decision works because picking the largest reward among currently feasible tasks maximizes future opportunities.

The algorithm processes tasks in requirement order while the heap handles reward prioritization. Each task is inserted and removed from the heap at most once. That results in O(n log n) time due to sorting and heap operations, and O(n) space for the heap.

Recommended for interviews: The greedy strategy with sorting and a max heap is what interviewers expect. It shows you can combine greedy algorithms with sorting and a priority queue to manage dynamically available choices. Mentioning the brute force idea first demonstrates understanding of the search space, while the heap optimization proves you can reduce it to O(n log n).