Optimal Decaying Task Scheduling

hard

You are given a list of tasks and a maximum available time limit $T$.

Each task is defined by a triplet [time, value, decay]:

time ($t_i > 0$): The duration required to complete the task.
value ($v_i \ge 0$): The base reward earned upon completing the task.
decay ($d_i \ge 0$): The reward loss rate per unit of elapsed time.

When a selected task $i$ completes at cumulative time $C$ (the sum of execution times of task $i$ and all tasks executed before it), its realized reward is $v_i - d_i \cdot C$.

You can select any subset of tasks and execute them in any order, provided that the total execution time of all selected tasks does not exceed $T$.

Return the maximum possible sum of realized rewards obtainable. If executing no tasks is optimal or all achievable sums are negative, return 0.

Example 1

Input

[
  "[[2, 10, 1], [3, 20, 3], [1, 5, 2]]",
  "5"
]

Output

Explanation. Tasks sorted by decay-to-time ratio d/t are task 2 (ratio 2/1 = 2.0), task 1 (3/3 = 1.0), task 0 (1/2 = 0.5). Selecting task 1 followed by task 0 yields completion times 3 and 5. Total reward = (20 - 3*3) + (10 - 1*5) = 11 + 5 = 16 within total time 5.

Example 2

Input

[
  "[[5, 100, 10], [5, 100, 1]]",
  "5"
]

Output

Explanation. Only one task can fit in time limit 5. The second task finishes at time 5 with reward 100 - 1*5 = 95, which is better than the first task (100 - 10*5 = 50).

Example 3

Input

[
  "[[4, 10, 5], [2, 15, 2], [3, 20, 1]]",
  "10"
]

Output

Explanation. Selecting task 1 ([2, 15, 2]) and task 2 ([3, 20, 1]) in custom sorted order gives completion times 2 and 5. Reward = (15 - 2*2) + (20 - 1*5) = 11 + 15 = 26.

Example 4

Input

[
  "[[10, 50, 10]]",
  "5"
]

Output

Explanation. The required time (10) exceeds max time T=5, so no tasks can be selected.

Example 5

Input

[
  "[[2, 30, 5], [2, 30, 5]]",
  "4"
]

Output

Explanation. Executing both identical tasks takes total time 4. First task completes at t=2 (reward 20), second at t=4 (reward 10). Total reward = 30.

Follow-up: How would you solve the problem if the decay rate was compounding/multiplicative ($v_i \cdot \gamma^C$) instead of additive linear, or if task dependencies formed a Directed Acyclic Graph (DAG)?

Constraints:

- $1 \le \text{tasks.length} \le 1000$ - $1 \le T \le 2000$ - For each task `[time, value, decay]`: - $1 \le \text{time} \le 2000$ - $0 \le \text{value} \le 10000$ - $0 \le \text{decay} \le 100$

Views: 3