LeetCode 3767 - Maximize Points After Choosing K Tasks

The problem gives two integer arrays, technique1 and technique2, each of length n, representing two ways to complete n tasks. Completing the ith task with technique1 yields technique1[i] points, while using technique2 yields technique2[i] points.

leetcodemediumarraygreedysortingheap-(priority-queue)

LeetCode Problem 3767

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting, Heap (Priority Queue)

Solution

Problem Understanding

The problem gives two integer arrays, technique1 and technique2, each of length n, representing two ways to complete n tasks. Completing the ith task with technique1 yields technique1[i] points, while using technique2 yields technique2[i] points. You are also given an integer k, which specifies the minimum number of tasks that must be completed using technique1. The objective is to maximize the total points earned while satisfying the constraint of completing at least k tasks with technique1.

The input guarantees that n is between 1 and 10^5, the point values are between 1 and 10^5, and k is between 0 and n. This implies that a brute-force approach that examines all subsets of tasks will be too slow. Edge cases include k = 0 where no task is required to use technique1, k = n where all tasks must use technique1, and situations where technique2[i] > technique1[i] for many tasks, which may tempt a naive greedy choice without satisfying the k constraint.

The key challenge is deciding which tasks to force to use technique1 versus which tasks to allow to use the higher-scoring technique for each task, while respecting the minimum k requirement.

Approaches

The brute-force approach would enumerate all subsets of tasks of size at least k to assign to technique1, compute total scores for each combination, and pick the maximum. This is correct but impractical because it has exponential complexity O(2^n) and cannot handle n up to 10^5.

The optimal approach uses a greedy strategy based on the difference in points between techniques for each task. Define diff[i] = technique1[i] - technique2[i]. A positive difference means technique1 is better, while a negative difference favors technique2. To maximize points while satisfying the k constraint, we should sort tasks by diff[i] in descending order. Assign technique1 to the first k tasks with the largest positive differences (guaranteeing the minimum requirement) and then choose the higher-scoring technique for remaining tasks. This ensures that the tasks we are forced to assign to technique1 are the ones that lose the least if we choose technique1, while all other tasks pick whichever technique gives more points.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Enumerate all subsets of size ≥ k and sum points; infeasible for large n
Optimal O(n log n) O(n) Sort tasks by technique1[i] - technique2[i] and assign techniques greedily

Algorithm Walkthrough

  1. Compute the difference array diff[i] = technique1[i] - technique2[i] for all tasks. This captures the benefit of using technique1 over technique2.
  2. Pair each task with its index and difference for sorting purposes.
  3. Sort the tasks in descending order of diff. Tasks with the largest difference appear first because assigning technique1 to them is most valuable.
  4. Initialize total_points = 0.
  5. Iterate over the sorted tasks. For the first k tasks (ensuring the minimum requirement), add technique1[i] to total_points.
  6. For the remaining tasks, if diff[i] > 0 (technique1 is better), add technique1[i]; otherwise, add technique2[i].
  7. Return total_points.

Why it works: Sorting by technique1 - technique2 ensures that the tasks that benefit the most from technique1 are prioritized for mandatory assignment. For remaining tasks, always picking the higher-scoring technique ensures that the total points are maximized. This greedy approach respects the k constraint while ensuring optimality because each decision is locally optimal and affects only that task’s contribution.

Python Solution

from typing import List

class Solution:
    def maxPoints(self, technique1: List[int], technique2: List[int], k: int) -> int:
        n = len(technique1)
        # Compute difference array with indices
        tasks = [(technique1[i] - technique2[i], i) for i in range(n)]
        # Sort tasks by difference descending
        tasks.sort(reverse=True)
        
        total_points = 0
        for idx, (diff, i) in enumerate(tasks):
            if idx < k:
                # First k tasks must use technique1
                total_points += technique1[i]
            else:
                # Use whichever technique gives more points
                total_points += max(technique1[i], technique2[i])
        return total_points

Implementation walkthrough: The tasks array holds tuples of (difference, index) to maintain a mapping back to the original arrays. Sorting ensures that the largest differences come first, which allows us to satisfy the k constraint optimally. The iteration handles the forced technique1 assignments and then selects the higher-scoring technique for remaining tasks.

Go Solution

import "sort"

func maxPoints(technique1 []int, technique2 []int, k int) int64 {
    n := len(technique1)
    type Task struct {
        diff int
        index int
    }
    
    tasks := make([]Task, n)
    for i := 0; i < n; i++ {
        tasks[i] = Task{technique1[i] - technique2[i], i}
    }
    
    sort.Slice(tasks, func(i, j int) bool {
        return tasks[i].diff > tasks[j].diff
    })
    
    var total int64 = 0
    for idx, task := range tasks {
        if idx < k {
            total += int64(technique1[task.index])
        } else {
            if technique1[task.index] > technique2[task.index] {
                total += int64(technique1[task.index])
            } else {
                total += int64(technique2[task.index])
            }
        }
    }
    return total
}

Go-specific notes: We define a Task struct to store diff and index. sort.Slice is used for custom sorting. int64 is used for total accumulation to prevent overflow when sums of large numbers exceed int.

Worked Examples

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

Task technique1 technique2 diff (t1 - t2)
0 5 10 -5
1 2 3 -1
2 10 8 2

Sort by diff descending: task 2 (2), task 1 (-1), task 0 (-5)

  • First k=2 tasks must use technique1: task 2 → 10, task 1 → 2
  • Remaining task 0: max(5,10) = 10
  • Total = 10 + 2 + 10 = 22

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

  • Differences: [5,5,5]
  • Sorted: [0,1,2] (any order)
  • First k=2 tasks use technique1: 10+20=30
  • Remaining task: max(30,25)=30
  • Total = 10+20+30=60

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

  • Differences: [-3,-3,-3]
  • k=0, no forced technique1
  • Choose max for all: 4+5+6=15

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting n tasks dominates runtime; computing differences is O(n)
Space O(n) Storing the difference array or Task structs

The algorithm is efficient for n up to 10^5 because sorting is O(n log n) and no nested loops are used.

Test Cases

# Provided examples
assert Solution().maxPoints([5,2,10], [10,3,8], 2) == 22  # Example 1
assert Solution().maxPoints([10,20,30], [5,15,25], 2) == 60  # Example 2
assert Solution().maxPoints([1,2,3], [4,5,6], 0) == 15  # Example 3

# Edge cases
assert Solution().maxPoints([1], [100], 0) == 100  # Single task, choose max
assert Solution().maxPoints([1], [100], 1) == 1    # Single task, forced technique1
assert Solution().maxPoints([10,10,10], [10,10,10], 2) == 30  # Equal points
assert Solution().maxPoints([100,1,1