Optimal Intervention Schedule
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.
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.
maxNetHealthGain function.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.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.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
Example 1
Input:
scores = [10, 5, 8, 12], costs = [2, 3, 1, 4], k = 1
Output:
16
Note:
Consider the following sequence of interventions:
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.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.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.
Example 3
Input:
scores = [20, 10, 30, 5, 40], costs = [5, 2, 8, 1, 10], k = 2
Output:
45
Note:
Optimal interventions:
scores[0] - costs[0] = 20 - 5 = 15. Next possible intervention: Day 0 + 2 + 1 = 3.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
1 <= N <= 10^5 (where N is the length of scores and costs)0 <= scores[i] <= 10^40 <= costs[i] <= 10^40 <= k < Nk and array boundaries.Loading editor...