Maximize Campaign Reach
As a marketing agency, optimizing campaign reach is crucial. You're tasked with selecting advertising slots for an upcoming campaign to maximize the total audience reach. Each available slot has a defined start time, end time, and an estimated audience reach. The primary constraint is that only one advertisement can run at any given time; therefore, selected slots must not overlap.
This problem challenges your ability to identify an optimal selection strategy under specific constraints, a common scenario in resource allocation and scheduling.
Implement a function maximizeCampaignReach that takes an array of campaign slots and returns the maximum total audience reach achievable by selecting a non-overlapping subset of these slots.
Input:
campaignSlots: An array of arrays, where each inner array [startTime, endTime, reach] represents an available advertising slot.
startTime: An integer representing the start time of the slot.endTime: An integer representing the end time of the slot.reach: An integer representing the estimated audience reach for this slot.Output: A single integer representing the maximum total audience reach.
[s1, e1, r1] and [s2, e2, r2] are considered non-overlapping if e1 <= s2 or e2 <= s1. This means a slot ending at time X and another starting at time X are considered non-overlapping.campaignSlots is empty, the function should return 0.startTime and endTime are non-negative integers. startTime will always be strictly less than endTime for any given slot.reach values are positive integers.Examples
Example 1
Input:
campaignSlots = [[1, 5, 100], [6, 10, 200], [2, 7, 50]]
Output:
300
Note:
Sorted by end time: [[1, 5, 100], [2, 7, 50], [6, 10, 200]]. We pick [1, 5, 100] (reach 100, last end 5). Then, [2, 7, 50] overlaps. Finally, pick [6, 10, 200] (reach 200, last end 10). Total reach = 100 + 200 = 300.
Example 2
Input:
campaignSlots = [[1, 3, 10], [2, 4, 20], [3, 5, 30]]
Output:
40
Note:
Sorted by end time: [[1, 3, 10], [2, 4, 20], [3, 5, 30]]. We pick [1, 3, 10] (reach 10, last end 3). [2, 4, 20] overlaps. Pick [3, 5, 30] (reach 30, last end 5). Total reach = 10 + 30 = 40.
Example 3
Input:
campaignSlots = [[10, 20, 500], [1, 5, 100], [3, 8, 200], [21, 25, 10]]
Output:
610
Note:
Sorted by end time: [[1, 5, 100], [3, 8, 200], [10, 20, 500], [21, 25, 10]]. Pick [1, 5, 100] (reach 100, last end 5). [3, 8, 200] overlaps. Pick [10, 20, 500] (reach 500, last end 20). Pick [21, 25, 10] (reach 10, last end 25). Total reach = 100 + 500 + 10 = 610.
Constraints
1 <= campaignSlots.length <= 10^50 <= startTime < endTime <= 10^91 <= reach <= 10^4reach values can exceed the capacity of a 32-bit integer, so use a data type that supports larger numbers (e.g., number in JavaScript/TypeScript).startTime >= endTime, non-integer values).Loading editor...