<p>You are given two <strong>1-indexed</strong> integer arrays, <code>nums</code> and, <code>changeIndices</code>, having lengths <code>n</code> and <code>m</code>, respectively.</p>

<p>Initially, all indices in <code>nums</code> are unmarked. Your task is to mark <strong>all</strong> indices in <code>nums</code>.</p>

<p>In each second, <code>s</code>, in order from <code>1</code> to <code>m</code> (<strong>inclusive</strong>), you can perform <strong>one</strong> of the following operations:</p>

<ul>
	<li>Choose an index <code>i</code> in the range <code>[1, n]</code> and <strong>decrement</strong> <code>nums[i]</code> by <code>1</code>.</li>
	<li>Set <code>nums[changeIndices[s]]</code> to any <strong>non-negative</strong> value.</li>
	<li>Choose an index <code>i</code> in the range <code>[1, n]</code>, where <code>nums[i]</code> is <strong>equal</strong> to <code>0</code>, and <strong>mark</strong> index <code>i</code>.</li>
	<li>Do nothing.</li>
</ul>

<p>Return <em>an integer denoting the <strong>earliest second</strong> in the range </em><code>[1, m]</code><em> when <strong>all</strong> indices in </em><code>nums</code><em> can be marked by choosing operations optimally, or </em><code>-1</code><em> if it is impossible.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [3,2,3], changeIndices = [1,3,2,2,2,2,3]
<strong>Output:</strong> 6
<strong>Explanation:</strong> In this example, we have 7 seconds. The following operations can be performed to mark all indices:
Second 1: Set nums[changeIndices[1]] to 0. nums becomes [0,2,3].
Second 2: Set nums[changeIndices[2]] to 0. nums becomes [0,2,0].
Second 3: Set nums[changeIndices[3]] to 0. nums becomes [0,0,0].
Second 4: Mark index 1, since nums[1] is equal to 0.
Second 5: Mark index 2, since nums[2] is equal to 0.
Second 6: Mark index 3, since nums[3] is equal to 0.
Now all indices have been marked.
It can be shown that it is not possible to mark all indices earlier than the 6th second.
Hence, the answer is 6.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [0,0,1,2], changeIndices = [1,2,1,2,1,2,1,2]
<strong>Output:</strong> 7
<strong>Explanation:</strong> In this example, we have 8 seconds. The following operations can be performed to mark all indices:
Second 1: Mark index 1, since nums[1] is equal to 0.
Second 2: Mark index 2, since nums[2] is equal to 0.
Second 3: Decrement index 4 by one. nums becomes [0,0,1,1].
Second 4: Decrement index 4 by one. nums becomes [0,0,1,0].
Second 5: Decrement index 3 by one. nums becomes [0,0,0,0].
Second 6: Mark index 3, since nums[3] is equal to 0.
Second 7: Mark index 4, since nums[4] is equal to 0.
Now all indices have been marked.
It can be shown that it is not possible to mark all indices earlier than the 7th second.
Hence, the answer is 7.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3], changeIndices = [1,2,3]
<strong>Output:</strong> -1
<strong>Explanation: </strong>In this example, it can be shown that it is impossible to mark all indices, as we don&#39;t have enough seconds. 
Hence, the answer is -1.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n == nums.length &lt;= 5000</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>1 &lt;= m == changeIndices.length &lt;= 5000</code></li>
	<li><code>1 &lt;= changeIndices[i] &lt;= n</code></li>
</ul>

class Solution:
    def earliestSecondToMarkIndices(self, nums: List[int], changeIndices: List[int]) -> int:
        # Decrement changeIndices to make them zero-indexed
        for i in range(len(changeIndices)):
            changeIndices[i] -= 1

        # Pre-compute when each index of nums first appears in changeIndices with a value > 1
        # This indicates when we plan to use the set operation on the number to set it to zero
        first_occurrence = [-1] * len(nums)
        for i in range(len(changeIndices)):
            if nums[changeIndices[i]] > 1 and first_occurrence[changeIndices[i]] == -1:
                first_occurrence[changeIndices[i]] = i

        # Compute the total time needed if we cannot use the set operation
        total_time_needed = len(nums)  # Time to mark each number
        for n in nums:
            total_time_needed += n  # Time for subtracting 1, n times

        # Check if it is possible to mark all indices within the total time needed
        if not self._is_possible(nums, changeIndices, len(changeIndices), first_occurrence, total_time_needed):
            return -1

        # Binary search for the fastest time
        fastest = 0
        slowest = len(changeIndices)
        while fastest < slowest:
            mid_time = (fastest + slowest) // 2
            if self._is_possible(nums, changeIndices, mid_time, first_occurrence, total_time_needed):
                slowest = mid_time
            else:
                fastest = mid_time + 1

        return fastest

    def _is_possible(self, nums: List[int], changeIndices: List[int], max_time: int, first_occurrence: List[int], total_time_needed: int) -> bool:
        # Priority queue to hold the numbers that we have zeroed with the set operation
        pq = []
        heapq.heapify(pq)
        
        # Count of time steps where a number was zeroed earlier
        already_zeroed = 0
        
        # Start from max_time and work backwards
        for i in range(max_time - 1, -1, -1):
            index = changeIndices[i]
            if first_occurrence[index] != i:
                # The index was zeroed earlier in time
                already_zeroed += 1
                continue
            
            # First opportunity to set nums[index] = 0, which reduces the time needed
            total_time_needed -= nums[index] - 1  # Subtract 1 since we use a timestep to make zero
            heapq.heappush(pq, nums[index])
            
            # If pq size is greater than already_zeroed, we are zeroing too many at the end
            # without saving enough time to mark, so find the smallest value which was previously zeroed and undo it
            if len(pq) > already_zeroed:
                total_time_needed += heapq.heappop(pq) - 1
                already_zeroed += 1
        
        return total_time_needed <= max_time        
108