We need at least n seconds, and at most sum(nums[i]) + n seconds.
提示 2
We can binary search the earliest second where all indices can be marked.
提示 3
If there is an operation where we change nums[changeIndices[i]] to a non-negative value, it is best for it to satisfy the following constraints:
nums[changeIndices[i]] should not be equal to 0.
nums[changeIndices[i]] should be changed to 0.
It should be the first position where changeIndices[i] occurs in changeIndices.
There should be another second, j, where changeIndices[i] will be marked. j is in the range [i + 1, m].
提示 4
Let time_needed = sum(nums[i]) + n. To check if we can mark all indices at some second x, we need to make time_needed <= x, using non-negative change operations as described previously.
提示 5
Using a non-negative change operation on some nums[changeIndices[i]] that satisfies the constraints described previously reduces time_needed by nums[changeIndices[i]] - 1. So, we need to maximize the sum of (nums[changeIndices[i]] - 1) while ensuring that the non-negative change operations still satisfy the constraints.
提示 6
Maximizing the sum of (nums[changeIndices[i]] - 1) can be done greedily using a min-priority queue and going in reverse starting from second x to second 1, maximizing the sum of the values in the priority queue and ensuring that for every non-negative change operation on nums[changeIndices[i]] chosen, there is another second j in the range [i + 1, x] where changeIndices[i] can be marked.
提示 7
The answer is the first value of x in the range [1, m] where it is possible to make time_needed <= x, or -1 if there is no such second.
