3049. Earliest Second to Mark Indices II Hard

1/**
2 * [3049] Earliest Second to Mark Indices II
3 *
4 * You are given two 1-indexed integer arrays, nums and, changeIndices, having lengths n and m, respectively.
5 * Initially, all indices in nums are unmarked. Your task is to mark all indices in nums.
6 * In each second, s, in order from 1 to m (inclusive), you can perform one of the following operations:
7 * 
8 * 	Choose an index i in the range [1, n] and decrement nums[i] by 1.
9 * 	Set nums[changeIndices[s]] to any non-negative value.
10 * 	Choose an index i in the range [1, n], where nums[i] is equal to 0, and mark index i.
11 * 	Do nothing.
12 * 
13 * Return an integer denoting the earliest second in the range [1, m] when all indices in nums can be marked by choosing operations optimally, or -1 if it is impossible.
14 *  
15 * <strong class="example">Example 1:
16 * 
17 * Input: nums = [3,2,3], changeIndices = [1,3,2,2,2,2,3]
18 * Output: 6
19 * Explanation: In this example, we have 7 seconds. The following operations can be performed to mark all indices:
20 * Second 1: Set nums[changeIndices[1]] to 0. nums becomes [0,2,3].
21 * Second 2: Set nums[changeIndices[2]] to 0. nums becomes [0,2,0].
22 * Second 3: Set nums[changeIndices[3]] to 0. nums becomes [0,0,0].
23 * Second 4: Mark index 1, since nums[1] is equal to 0.
24 * Second 5: Mark index 2, since nums[2] is equal to 0.
25 * Second 6: Mark index 3, since nums[3] is equal to 0.
26 * Now all indices have been marked.
27 * It can be shown that it is not possible to mark all indices earlier than the 6th second.
28 * Hence, the answer is 6.
29 * 
30 * <strong class="example">Example 2:
31 * 
32 * Input: nums = [0,0,1,2], changeIndices = [1,2,1,2,1,2,1,2]
33 * Output: 7
34 * Explanation: In this example, we have 8 seconds. The following operations can be performed to mark all indices:
35 * Second 1: Mark index 1, since nums[1] is equal to 0.
36 * Second 2: Mark index 2, since nums[2] is equal to 0.
37 * Second 3: Decrement index 4 by one. nums becomes [0,0,1,1].
38 * Second 4: Decrement index 4 by one. nums becomes [0,0,1,0].
39 * Second 5: Decrement index 3 by one. nums becomes [0,0,0,0].
40 * Second 6: Mark index 3, since nums[3] is equal to 0.
41 * Second 7: Mark index 4, since nums[4] is equal to 0.
42 * Now all indices have been marked.
43 * It can be shown that it is not possible to mark all indices earlier than the 7th second.
44 * Hence, the answer is 7.
45 * 
46 * <strong class="example">Example 3:
47 * 
48 * Input: nums = [1,2,3], changeIndices = [1,2,3]
49 * Output: -1
50 * Explanation: In this example, it can be shown that it is impossible to mark all indices, as we don't have enough seconds. 
51 * Hence, the answer is -1.
52 * 
53 *  
54 * Constraints:
55 * 
56 * 	1 <= n == nums.length <= 5000
57 * 	0 <= nums[i] <= 10^9
58 * 	1 <= m == changeIndices.length <= 5000
59 * 	1 <= changeIndices[i] <= n
60 * 
61 */
62pub struct Solution {}
63
64// problem: https://leetcode.com/problems/earliest-second-to-mark-indices-ii/
65// discuss: https://leetcode.com/problems/earliest-second-to-mark-indices-ii/discuss/?currentPage=1&orderBy=most_votes&query=
66
67// submission codes start here
68
69impl Solution {
70    pub fn earliest_second_to_mark_indices(nums: Vec<i32>, change_indices: Vec<i32>) -> i32 {
71        0
72    }
73}
74
75// submission codes end
76
77#[cfg(test)]
78mod tests {
79    use super::*;
80
81    #[test]
82    fn test_3049() {
83    }
84}
85