3645. Maximum Total from Optimal Activation Order Medium
1/**
2 * [3645] Maximum Total from Optimal Activation Order
3 *
4 * You are given two integer arrays value and limit, both of length n.
5 * Initially, all elements are inactive. You may activate them in any order.
6 *
7 * To activate an inactive element at index i, the number of currently active elements must be strictly less than limit[i].
8 * When you activate the element at index i, it adds value[i] to the total activation value (i.e., the sum of value[i] for all elements that have undergone activation operations).
9 * After each activation, if the number of currently active elements becomes x, then all elements j with limit[j] <= x become permanently inactive, even if they are already active.
10 *
11 * Return the maximum total you can obtain by choosing the activation order optimally.
12 *
13 * <strong class="example">Example 1:
14 * <div class="example-block">
15 * Input: <span class="example-io">value = [3,5,8], limit = [2,1,3]</span>
16 * Output: <span class="example-io">16</span>
17 * Explanation:
18 * One optimal activation order is:
19 * <table>
20 * <thead>
21 * <tr>
22 * <th align="center" style="border: 1px solid black;">Step</th>
23 * <th align="center" style="border: 1px solid black;">Activated i</th>
24 * <th align="center" style="border: 1px solid black;">value[i]</th>
25 * <th align="center" style="border: 1px solid black;">Active Before i</th>
26 * <th align="center" style="border: 1px solid black;">Active After i</th>
27 * <th align="center" style="border: 1px solid black;">Becomes Inactive j</th>
28 * <th align="center" style="border: 1px solid black;">Inactive Elements</th>
29 * <th align="center" style="border: 1px solid black;">Total</th>
30 * </tr>
31 * </thead>
32 * <tbody>
33 * <tr>
34 * <td align="center" style="border: 1px solid black;">1</td>
35 * <td align="center" style="border: 1px solid black;">1</td>
36 * <td align="center" style="border: 1px solid black;">5</td>
37 * <td align="center" style="border: 1px solid black;">0</td>
38 * <td align="center" style="border: 1px solid black;">1</td>
39 * <td align="center" style="border: 1px solid black;">j = 1 as limit[1] = 1</td>
40 * <td align="center" style="border: 1px solid black;">[1]</td>
41 * <td align="center" style="border: 1px solid black;">5</td>
42 * </tr>
43 * <tr>
44 * <td align="center" style="border: 1px solid black;">2</td>
45 * <td align="center" style="border: 1px solid black;">0</td>
46 * <td align="center" style="border: 1px solid black;">3</td>
47 * <td align="center" style="border: 1px solid black;">0</td>
48 * <td align="center" style="border: 1px solid black;">1</td>
49 * <td align="center" style="border: 1px solid black;">-</td>
50 * <td align="center" style="border: 1px solid black;">[1]</td>
51 * <td align="center" style="border: 1px solid black;">8</td>
52 * </tr>
53 * <tr>
54 * <td align="center" style="border: 1px solid black;">3</td>
55 * <td align="center" style="border: 1px solid black;">2</td>
56 * <td align="center" style="border: 1px solid black;">8</td>
57 * <td align="center" style="border: 1px solid black;">1</td>
58 * <td align="center" style="border: 1px solid black;">2</td>
59 * <td align="center" style="border: 1px solid black;">j = 0 as limit[0] = 2</td>
60 * <td align="center" style="border: 1px solid black;">[0, 1]</td>
61 * <td align="center" style="border: 1px solid black;">16</td>
62 * </tr>
63 * </tbody>
64 * </table>
65 * Thus, the maximum possible total is 16.
66 * </div>
67 * <strong class="example">Example 2:
68 * <div class="example-block">
69 * Input: <span class="example-io">value = [4,2,6], limit = [1,1,1]</span>
70 * Output: <span class="example-io">6</span>
71 * Explanation:
72 * One optimal activation order is:
73 * <table style="border: 1px solid black;">
74 * <thead>
75 * <tr>
76 * <th align="center" style="border: 1px solid black;">Step</th>
77 * <th align="center" style="border: 1px solid black;">Activated i</th>
78 * <th align="center" style="border: 1px solid black;">value[i]</th>
79 * <th align="center" style="border: 1px solid black;">Active Before i</th>
80 * <th align="center" style="border: 1px solid black;">Active After i</th>
81 * <th align="center" style="border: 1px solid black;">Becomes Inactive j</th>
82 * <th align="center" style="border: 1px solid black;">Inactive Elements</th>
83 * <th align="center" style="border: 1px solid black;">Total</th>
84 * </tr>
85 * </thead>
86 * <tbody>
87 * <tr>
88 * <td align="center" style="border: 1px solid black;">1</td>
89 * <td align="center" style="border: 1px solid black;">2</td>
90 * <td align="center" style="border: 1px solid black;">6</td>
91 * <td align="center" style="border: 1px solid black;">0</td>
92 * <td align="center" style="border: 1px solid black;">1</td>
93 * <td align="center" style="border: 1px solid black;">j = 0, 1, 2 as limit[j] = 1</td>
94 * <td align="center" style="border: 1px solid black;">[0, 1, 2]</td>
95 * <td align="center" style="border: 1px solid black;">6</td>
96 * </tr>
97 * </tbody>
98 * </table>
99 * Thus, the maximum possible total is 6.
100 * </div>
101 * <strong class="example">Example 3:
102 * <div class="example-block">
103 * Input: <span class="example-io">value = [4,1,5,2], limit = [3,3,2,3]</span>
104 * Output: <span class="example-io">12</span>
105 * Explanation:
106 * One optimal activation order is:
107 * <table style="border: 1px solid black;">
108 * <thead>
109 * <tr>
110 * <th align="center" style="border: 1px solid black;">Step</th>
111 * <th align="center" style="border: 1px solid black;">Activated i</th>
112 * <th align="center" style="border: 1px solid black;">value[i]</th>
113 * <th align="center" style="border: 1px solid black;">Active Before i</th>
114 * <th align="center" style="border: 1px solid black;">Active After i</th>
115 * <th align="center" style="border: 1px solid black;">Becomes Inactive j</th>
116 * <th align="center" style="border: 1px solid black;">Inactive Elements</th>
117 * <th align="center" style="border: 1px solid black;">Total</th>
118 * </tr>
119 * </thead>
120 * <tbody>
121 * <tr>
122 * <td align="center" style="border: 1px solid black;">1</td>
123 * <td align="center" style="border: 1px solid black;">2</td>
124 * <td align="center" style="border: 1px solid black;">5</td>
125 * <td align="center" style="border: 1px solid black;">0</td>
126 * <td align="center" style="border: 1px solid black;">1</td>
127 * <td align="center" style="border: 1px solid black;">-</td>
128 * <td align="center" style="border: 1px solid black;">[ ]</td>
129 * <td align="center" style="border: 1px solid black;">5</td>
130 * </tr>
131 * <tr>
132 * <td align="center" style="border: 1px solid black;">2</td>
133 * <td align="center" style="border: 1px solid black;">0</td>
134 * <td align="center" style="border: 1px solid black;">4</td>
135 * <td align="center" style="border: 1px solid black;">1</td>
136 * <td align="center" style="border: 1px solid black;">2</td>
137 * <td align="center" style="border: 1px solid black;">j = 2 as limit[2] = 2</td>
138 * <td align="center" style="border: 1px solid black;">[2]</td>
139 * <td align="center" style="border: 1px solid black;">9</td>
140 * </tr>
141 * <tr>
142 * <td align="center" style="border: 1px solid black;">3</td>
143 * <td align="center" style="border: 1px solid black;">1</td>
144 * <td align="center" style="border: 1px solid black;">1</td>
145 * <td align="center" style="border: 1px solid black;">1</td>
146 * <td align="center" style="border: 1px solid black;">2</td>
147 * <td align="center" style="border: 1px solid black;">-</td>
148 * <td align="center" style="border: 1px solid black;">[2]</td>
149 * <td align="center" style="border: 1px solid black;">10</td>
150 * </tr>
151 * <tr>
152 * <td align="center" style="border: 1px solid black;">4</td>
153 * <td align="center" style="border: 1px solid black;">3</td>
154 * <td align="center" style="border: 1px solid black;">2</td>
155 * <td align="center" style="border: 1px solid black;">2</td>
156 * <td align="center" style="border: 1px solid black;">3</td>
157 * <td align="center" style="border: 1px solid black;">j = 0, 1, 3 as limit[j] = 3</td>
158 * <td align="center" style="border: 1px solid black;">[0, 1, 2, 3]</td>
159 * <td align="center" style="border: 1px solid black;">12</td>
160 * </tr>
161 * </tbody>
162 * </table>
163 * Thus, the maximum possible total is 12.
164 * </div>
165 *
166 * Constraints:
167 *
168 * 1 <= n == value.length == limit.length <= 10^5
169 * 1 <= value[i] <= 10^5
170 * 1 <= limit[i] <= n
171 *
172 */
173pub struct Solution {}
174
175// problem: https://leetcode.com/problems/maximum-total-from-optimal-activation-order/
176// discuss: https://leetcode.com/problems/maximum-total-from-optimal-activation-order/discuss/?currentPage=1&orderBy=most_votes&query=
177
178// submission codes start here
179
180impl Solution {
181 pub fn max_total(value: Vec<i32>, limit: Vec<i32>) -> i64 {
182
183 }
184}
185
186// submission codes end
187
188#[cfg(test)]
189mod tests {
190 use super::*;
191
192 #[test]
193 fn test_3645() {
194 }
195}
196Back
© 2026 bowen.ge All Rights Reserved.