Minimize Points Used Across Multiple Reward Programs

Problem

A customer has several reward programs. Program i has at most balance[i] points, and each point is worth value[i] integer microdollars. Given a target in microdollars, return the minimum total number of points whose combined value is at least the target, or -1 if the available points cannot cover it.

Constraints & Assumptions

• There are between 1 and 100 reward programs.
• Balances are nonnegative integers and values are positive integers.
• All inputs and intermediate products stay within 2^53.
• Points are indivisible and each program's balance is a hard upper bound.

Clarifications

• Overpaying the target is allowed; the primary objective is fewest points.
• Any combination with the minimum point count is acceptable, so return only that count.
• Exchange values are already fixed for the transaction date.

Examples

target = 168_000_000
balance = [36_000, 12_000, 25_000]
value = [12_000, 9_000, 8_500]
output = 14_000
explanation: 14,000 points at 12,000 microdollars each reach the target.

Hints

Hint: Compare point values

Every point has the same objective cost of one, so consider whether using higher-value points first can ever hurt the minimum count.

Hint: Respect finite balances

Consume the most valuable available points in bounded groups and detect any remaining uncovered target.

Minimize Points Used Across Multiple Reward Programs

Hints

1. Since every selected point costs one in the objective, compare programs by value per point.
2. Consume higher-value points in bounded groups and report -1 if value remains uncovered after all groups.

Approach

Sort programs by descending value per point. While value remains uncovered, take as many points as needed from the current highest-value program, capped by that program's balance. For any fixed point count, selecting the available points with the greatest values maximizes covered value; therefore, if the first c points in this order cannot meet the target, no other c points can. The first time the greedy prefix reaches the target is consequently the minimum count. If all bounded supplies are exhausted first, coverage is impossible.

• Time complexity: O(p log p), where p is the number of reward programs.
• Space complexity: O(p) for the sorted program list.