Frontend School

Maximize Campaign Reach

DSA
medium

Maximize Campaign Reach

Medium
Greedy
Arrays
Sorting

Overview

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.

What you need to do / Task

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 & output

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.

Clarifications

  • Non-overlapping definition: Two slots [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.
  • Empty input: If campaignSlots is empty, the function should return 0.
  • Time values: startTime and endTime are non-negative integers. startTime will always be strictly less than endTime for any given slot.
  • Reach values: reach values are positive integers.

Examples

1

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.

2

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.

3

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

Constraints & assumptions

  • 1 <= campaignSlots.length <= 10^5
  • 0 <= startTime < endTime <= 10^9
  • 1 <= reach <= 10^4
  • The sum of reach 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).

Out of scope

  • Handling malformed input (e.g., startTime >= endTime, non-integer values).
  • Concurrency or multi-threading concerns.
  • Network communication or database interactions.

What interviewers evaluate

  • Correctness: The solution must accurately compute the maximum total reach for all valid inputs.
  • Efficiency: The solution should have an optimal time and space complexity for the given constraints.
  • Algorithmic Approach: Demonstrated understanding and application of a suitable greedy algorithm.
  • Code Quality: Clear, well-structured, and readable code with appropriate variable names.

Loading editor...