Frontend School

Optimal Intervention Schedule

DSA
hard

Optimal Intervention Schedule

Hard
Dynamic Programming
1D DP
Arrays

Overview

Innovaccer's mission is to accelerate care delivery transformation. One critical aspect is optimizing patient care plans. Imagine we have a patient's projected daily health scores and potential intervention costs. We need to strategically schedule medical interventions to maximize the patient's net health gain, considering a mandatory recovery period after each intervention. This problem challenges you to develop an optimal scheduling algorithm.

What you need to do / Task

Implement a function maxNetHealthGain that takes an array of daily health scores, an array of corresponding intervention costs, and a cooldown period k. The function should calculate the maximum possible net health gain achievable.

Deliverables:

  1. Implement the maxNetHealthGain function.
  2. Your solution must correctly handle all valid inputs as per constraints.
  3. Optimize for time and space complexity.

Input & output

  • Input:
    • scores: An array of integers scores[i] representing the projected health boost if an intervention is performed on day i. 0 <= i < N.
    • costs: An array of integers costs[i] representing the cost of performing an intervention on day i. 0 <= i < N.
    • k: An integer representing the mandatory cooldown period. If an intervention is performed on day i, the next possible intervention day is i + k + 1 or later.
  • Output: An integer representing the maximum possible net health gain.

Clarifications

  • The scores and costs arrays will always have the same length, denoted by N.
  • k can be 0, meaning an intervention on day i allows the next intervention on day i+1.
  • It's always an option to perform no interventions at all, yielding a net gain of 0. The optimal strategy should never result in a negative total gain; if all possible intervention combinations lead to a negative total, the function should return 0.

Examples

1

Example 1

Input:

scores = [10, 5, 8, 12], costs = [2, 3, 1, 4], k = 1

Output:

16

Note:

Consider the following sequence of interventions:

  1. Day 0: Perform intervention. Net gain: scores[0] - costs[0] = 10 - 2 = 8. Due to k=1 cooldown, the next intervention can only be on day 0 + 1 + 1 = 2 or later.
  2. Day 3: Perform intervention. Net gain: scores[3] - costs[3] = 12 - 4 = 8. This is allowed as day 3 (>=2) respects the cooldown from day 0. Total net health gain = 8 (from Day 0) + 8 (from Day 3) = 16. This strategy yields the maximum possible net gain.
2

Example 2

Input:

scores = [1, 1, 1, 1, 1], costs = [10, 10, 10, 10, 10], k = 0

Output:

0

Note:

All individual interventions result in a negative net gain (e.g., 1 - 10 = -9). The optimal strategy is to perform no interventions, resulting in 0 net gain.

3

Example 3

Input:

scores = [20, 10, 30, 5, 40], costs = [5, 2, 8, 1, 10], k = 2

Output:

45

Note:

Optimal interventions:

  1. Day 0: scores[0] - costs[0] = 20 - 5 = 15. Next possible intervention: Day 0 + 2 + 1 = 3.
  2. Day 4: scores[4] - costs[4] = 40 - 10 = 30. This is allowed as day 4 (>=3) respects the cooldown from day 0. Total net gain = 15 (from Day 0) + 30 (from Day 4) = 45.

Constraints

Constraints & assumptions

  • 1 <= N <= 10^5 (where N is the length of scores and costs)
  • 0 <= scores[i] <= 10^4
  • 0 <= costs[i] <= 10^4
  • 0 <= k < N
  • The return value will fit within a standard 32-bit signed integer.

What interviewers evaluate

  • Correctness of the dynamic programming approach and recurrence relation.
  • Efficiency of the solution in terms of time and space complexity.
  • Clarity and readability of the code.
  • Handling of edge cases, particularly related to the cooldown period k and array boundaries.

Loading editor...