Skip to main content
Talentd

Maximize Points After Choosing K Tasks - Solution & Explanation

MediumArrayGreedySortingHeap (Priority Queue)8 min readAsked at: Amazon
Practice this problem

Problem Statement

You are given two integer arrays, technique1 and technique2, each of length n, where n represents the number of tasks to complete.

  • If the ith task is completed using technique 1, you earn technique1[i] points.
  • If it is completed using technique 2, you earn technique2[i] points.

You are also given an integer k, representing the minimum number of tasks that must be completed using technique 1.

You must complete at least k tasks using technique 1 (they do not need to be the first k tasks).

The remaining tasks may be completed using either technique.

Return an integer denoting the maximum total points you can earn.

 

Example 1:

Input: technique1 = [5,2,10], technique2 = [10,3,8], k = 2

Output: 22

Explanation:

We must complete at least k = 2 tasks using technique1.

Choosing technique1[1] and technique1[2] (completed using technique 1), and technique2[0] (completed using technique 2), yields the maximum points: 2 + 10 + 10 = 22.

Example 2:

Input: technique1 = [10,20,30], technique2 = [5,15,25], k = 2

Output: 60

Explanation:

We must complete at least k = 2 tasks using technique1.

Choosing all tasks using technique 1 yields the maximum points: 10 + 20 + 30 = 60.

Example 3:

Input: technique1 = [1,2,3], technique2 = [4,5,6], k = 0

Output: 15

Explanation:

Since k = 0, we are not required to choose any task using technique1.

Choosing all tasks using technique 2 yields the maximum points: 4 + 5 + 6 = 15.

 

Constraints:

  • 1 <= n == technique1.length == technique2.length <= 105
  • 1 <= technique1[i], technique2ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹[i] <= 10ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹5
  • 0 <= k <= n

Approach Overview

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

Solution

We can first assign all tasks to technique 2, so the initial total score is sum_{i=0}^{n-1} technique2[i].

Then, we calculate the score increase for each task if it were completed using technique 1 instead, denoted as diff[i] = technique1[i] - technique2[i]. We sort this in descending order to obtain a sorted array of task indices idx.

Next, we select the first k tasks to be completed using technique 1 and add their score differences to the total score. For the remaining tasks, if a task can increase the score by using technique 1 (i.e., diff[i] geq 0), we also choose to complete it using technique 1.

The time complexity is O(n times log n), and the space complexity is O(n). Where n is the number of tasks.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force / BacktrackingO(n!)O(n)Conceptual baseline to understand all possible task orders
Greedy + Sorting + Max HeapO(n log n)O(n)General optimal solution when tasks unlock based on current points

Video Solution

Maximize Points After Choosing K Tasks | LeetCode 3767 | Biweekly Contest 171 ā€¢ Sanyam IIT Guwahati ā€¢ 507 views views

Watch 5 more video solutions ā†’

Frequently Asked Questions

Is Maximize Points After Choosing K Tasks easy or hard?
Maximize Points After Choosing K Tasks is generally classified as a medium difficulty problem. The challenge is recognizing the greedy pattern and combining sorting with a heap to manage dynamically available choices. Once the pattern is identified, the implementation is straightforward.
Maximize Points After Choosing K Tasks Python/Java solution
The implementation sorts tasks by requirement and uses a priority queue to store rewards. Python typically uses heapq with negated values to simulate a max heap, while Java uses PriorityQueue with a reverse comparator. Each iteration selects the largest reward among feasible tasks.
How to solve Maximize Points After Choosing K Tasks in O(n log n)?
First sort all tasks by their requirement. Maintain a pointer that scans the sorted list and a max heap storing rewards of tasks whose requirement is less than or equal to the current points. For each of the k selections, push newly available tasks into the heap and extract the maximum reward. Add it to your current points and continue.
What is the best approach for Maximize Points After Choosing K Tasks?
The most efficient solution uses a greedy strategy combined with sorting and a max heap. Sort tasks by their requirement, push rewards of all currently feasible tasks into a max heap, and repeatedly pick the highest reward task up to k times. This guarantees the maximum gain at each step while keeping future options open. The overall complexity is O(n log n).
Is Maximize Points After Choosing K Tasks asked at Google/Amazon/Meta?
Problems combining greedy selection with a priority queue appear frequently in interviews at companies like Google, Amazon, and Meta. This pattern is similar to well-known interview questions such as IPO or project selection problems where tasks unlock based on current resources.
What data structure is used in Maximize Points After Choosing K Tasks?
The key data structure is a max heap (priority queue). It stores rewards of all tasks that are currently feasible so the algorithm can quickly extract the highest reward task. Sorting the tasks by requirement is also essential to efficiently add newly available tasks.
What is the time complexity of Maximize Points After Choosing K Tasks?
The optimal solution runs in O(n log n) time. Sorting the tasks by requirement costs O(n log n), and each task may be inserted and removed from a priority queue once, which also contributes O(n log n). Space complexity is O(n) for the heap storing available rewards.

Ready to solve this problem?

Practice Maximize Points After Choosing K Tasks with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays