Ad Segment Optimization
Inmobi's ad platform helps advertisers reach their desired audience efficiently. A key challenge is optimizing campaign budgets to achieve specific reach goals. This problem simulates a simplified scenario where you need to determine the most cost-effective way to target a precise number of users for an ad campaign by selecting various audience segments.
Given a list of available audience segments, where each segment has a certain users count and an associated cost, and a targetUsers count, your task is to find the minimum total cost to reach exactly targetUsers. You can select any segment type multiple times. If it's not possible to reach the targetUsers exactly, you should indicate this.
Input:
segments: An array of objects, where each object represents an audience segment with two properties: users (number) and cost (number).targetUsers: A number representing the exact total number of users you need to reach.Output:
number representing the minimum total cost to reach targetUsers. If targetUsers cannot be reached exactly, return -1.targetUsers. For example, if targetUsers = 20 and you have a segment {users: 10, cost: 2}, you can select this segment twice for a total of 20 users and cost 4.targetUsers is 0? If targetUsers is 0, the minimum cost is 0, as no segments need to be selected.segments is empty? If segments is empty and targetUsers is greater than 0, it's impossible to reach the target, so return -1. If targetUsers is 0, return 0.Examples
Example 1
Input:
segments = [{users: 10, cost: 2}, {users: 20, cost: 3}], targetUsers = 30
Output:
5
Note:
To reach 30 users, you can select the segment with 10 users (cost 2) and the segment with 20 users (cost 3). Total cost = 2 + 3 = 5.
Example 2
Input:
segments = [{users: 5, cost: 1}, {users: 10, cost: 4}], targetUsers = 12
Output:
-1
Note:
It's impossible to reach exactly 12 users using combinations of segments with 5 and 10 users.
Example 3
Input:
segments = [{users: 3, cost: 5}, {users: 5, cost: 8}], targetUsers = 0
Output:
0
Note:
To reach 0 users, no segments are needed, so the cost is 0.
Example 4
Input:
segments = [{users: 7, cost: 10}], targetUsers = 21
Output:
30
Note:
To reach 21 users, you can select the segment with 7 users (cost 10) three times. Total cost = 10 * 3 = 30.
Constraints
1 <= segments.length <= 2001 <= segments[i].users <= 50001 <= segments[i].cost <= 10000 <= targetUsers <= 5000users and cost values are positive integers.targetUsers or segments.length beyond the specified constraints.users or cost values.targetUsers = 0 or when the target is unreachable.Loading editor...