Earliest Second to Mark Indices II
You are given two 1-indexed integer arrays, nums and changeIndices, having lengths n and m, respectively.
Initially, all indices in nums are unmarked. Your task is to mark all indices in nums.
In each second, s, in order from 1 to m (inclusive), you can perform one of the following operations:
- Choose an index
iin the range[1, n]and decrementnums[i]by1. - Set
nums[changeIndices[s]]to any non-negative value. - Choose an index
iin the range[1, n], wherenums[i]is equal to0, and mark indexi. - Do nothing.
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.
Example 1
Input
nums = [3,2,3], changeIndices = [1,3,2,2,2,2,3]Output
6By setting the first three referenced indices to 0 and then marking indices 1, 2, and 3, all indices can be marked by second 6 and not earlier.
Example 2
Input
nums = [0,0,1,2], changeIndices = [1,2,1,2,1,2,1,2]Output
7An optimal sequence marks indices 1 and 2, decrements indices 4 and 3 to 0, and marks the remaining indices by second 7, which is the earliest possible second.
Constraints
- 1 <= n == nums.length <= 5000
- 0 <= nums[i] <= 10^9
- 1 <= m == changeIndices.length <= 5000
- 1 <= changeIndices[i] <= n