Choose k Paired Indices to Maximize Sum Times Minimum
Company: DevRev
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Choose exactly k distinct indices shared by same-length arrays nums1 and nums2. The score is the sum of selected nums1 values multiplied by the minimum selected nums2 value. Return the greatest score as long long; the selected indices are not returned.
```cpp
class Solution {
public:
long long maxScore(vector<int>& nums1, vector<int>& nums2, int k);
};
```
### Examples
**Example 1:**
```text
Input: nums1 = [2,5,1], nums2 = [4,2,3], k = 2
Output: 14
Explanation: Choosing indices 0 and 1 yields(2+5)*min(4,2)=14; the other pairs score 9 and 12.
```
**Example 2:**
```text
Input: nums1 = [0,7], nums2 = [9,0], k = 1
Output: 0
Explanation: Both single-index scores are 0, which is the maximum.
```
### Constraints
- `1 <= nums1.length == nums2.length <= 100000`.
- `0 <= nums1[i], nums2[i] <= 100000`.
- `1 <= k <= n`.
### Clarifying Questions
- Must exactly `k` indices be selected? Yes.
- Do the two arrays use the same selected indices? Yes.
- Can entries be zero? Yes.
- What if several selections tie? Return their shared maximum score, not a selection.
```hint Check the boundary
For `k = 1`, check how the score simplifies for each index.
```
Overview: Choose exactly k shared indices to maximize the selected first-array sum multiplied by the selected second-array minimum.