Frontend School

Optimize Campaign Deployment Windows

DSA
hard

Optimize Campaign Deployment Windows

Hard
Intervals
Dynamic Programming
Greedy
Data Structures
Sweep Line

Overview

Salesforce Marketing Cloud helps customers manage and deploy targeted marketing campaigns. A critical aspect of this is efficiently scheduling campaign deployments to maximize customer engagement and business impact, especially when operational resources (deployment slots) are limited. This problem focuses on optimizing the selection of high-priority campaigns to deploy within a set of available time windows.

What you need to do / Task

Implement the function maximizeCampaignPriority that determines the maximum total priority of campaigns that can be deployed given a set of campaigns and a set of available deployment slots.

Here are the rules for deployment:

  1. Each campaign is defined by its preferred deployment window [start, end] and a priority value.
  2. Each available slot is defined by its time window [start, end].
  3. A campaign C = [c_start, c_end, c_priority] can only be deployed if its entire preferred window [c_start, c_end] fits within one available slot S = [s_start, s_end]. That is, s_start <= c_start AND c_end <= s_end.
  4. Each available slot can be used by at most one campaign.
  5. Each campaign can be deployed at most once.
  6. The objective is to select a set of deployments such that the sum of priorities of all deployed campaigns is maximized.

Input & output

Function Signature (TypeScript): function maximizeCampaignPriority(campaigns: number[][], availableSlots: number[][]): number

Parameters:

  • campaigns: An array of arrays, where each inner array [start, end, priority] represents a campaign's preferred deployment window and its priority. start and end are integers representing time points (e.g., minutes from midnight).
  • availableSlots: An array of arrays, where each inner array [start, end] represents an available deployment time slot. start and end are integers representing time points.

Return Value:

  • A single integer representing the maximum total priority of campaigns that can be deployed.

Clarifications

  • Time values (start, end) are non-negative integers. start < end for all intervals.
  • Intervals are inclusive [start, end].
  • If no campaigns can be deployed, the function should return 0.

Examples

1

Example 1

Input:

campaigns = [[0, 5, 10], [3, 8, 5]], availableSlots = [[0, 10]]

Output:

10

Note:

Campaign [0,5,10] fits in slot [0,10], giving priority 10. Campaign [3,8,5] also fits in slot [0,10], but the slot can only be used once. Choosing [0,5,10] yields higher priority.

2

Example 2

Input:

campaigns = [[0, 2, 10], [1, 3, 100], [0, 1, 5]], availableSlots = [[0, 3], [0, 2]]

Output:

105

Note:

Valid assignments:

  • C0=[0,2,10] fits S0=[0,3] (P=10)
  • C0=[0,2,10] fits S1=[0,2] (P=10)
  • C1=[1,3,100] fits S0=[0,3] (P=100)
  • C2=[0,1,5] fits S0=[0,3] (P=5)
  • C2=[0,1,5] fits S1=[0,2] (P=5)

Optimal strategy: Assign C1=[1,3,100] to S0=[0,3] (P=100). Then assign C0=[0,2,10] to S1=[0,2] (P=10). Total priority = 100 + 10 = 110. Wait, C0=[0,2,10] cannot fit S1=[0,2] if the slot is [0,2] and campaign is [0,2]. Yes, it can. C2 also fits S1.

Let's re-evaluate: If C1 (100) takes S0, then S1 is remaining. S1 ([0,2]) can fit C0 ([0,2,10]) or C2 ([0,1,5]). C0 has higher priority (10 vs 5). So, C0 takes S1. Total: 100 + 10 = 110.

What if C0 (10) takes S0? Then S1 is remaining. S1 ([0,2]) can fit C2 ([0,1,5]). Total: 10 + 5 = 15. This is worse.

What if C0 (10) takes S1? Then S0 is remaining. S0 ([0,3]) can fit C1 ([1,3,100]) or C2 ([0,1,5]). C1 has higher priority (100 vs 5). So, C1 takes S0. Total: 10 + 100 = 110.

The output should be 110. My explanation had a typo, updated it. The example shows that a simple greedy choice (e.g., always picking the highest priority campaign for the first available slot) might not be optimal globally. Corrected output to 110.

3

Example 3

Input:

campaigns = [[10, 20, 100], [0, 5, 200]], availableSlots = [[0, 5], [10, 20]]

Output:

300

Note:

Campaign [0,5,200] fits in slot [0,5]. Campaign [10,20,100] fits in slot [10,20]. Both can be deployed independently, maximizing total priority to 200 + 100 = 300.

Constraints

Constraints & assumptions

  • 1 <= campaigns.length <= 10^4
  • 1 <= availableSlots.length <= 10^4
  • 0 <= start < end <= 10^9 (Time coordinates can be large, requiring coordinate compression or algorithms that don't depend on direct indexing of time).
  • 1 <= priority <= 1000
  • All input intervals are valid (start < end).
  • campaigns and availableSlots arrays are not necessarily sorted.

Out of scope

  • Validating input formats (e.g., start >= end).
  • Handling invalid or negative time/priority values.

What interviewers evaluate

  • Correctness and robustness of the interval matching logic.
  • Efficiency in handling potentially large numbers of campaigns and slots (N, M <= 10^4).
  • Ability to identify and apply an appropriate algorithmic paradigm (e.g., sweep line, dynamic programming, or a greedy approach with optimized data structures).
  • Clarity of code structure, effective use of data structures, and handling of edge cases.

Loading editor...