Earliest second to mark indices ii

use std::collections::BinaryHeap;
use std::cmp::Reverse;

impl Solution {
  pub fn earliest_second_to_mark_indices(nums: Vec<i32>, change_indices: Vec<i32>) -> i32 {
    let n = nums.len();
    let m = change_indices.len();

    // Key insight: if we fast-mark index i (use set to zero it then mark it),
    // it is optimal to use the FIRST occurrence of i in changeIndices for the set-op.
    // This frees all later occurrences as regular free seconds.
    //
    // Binary search on budget t. For a given t, check feasibility:
    //   1. Compute first_occ[i] = first index in changeIndices[0..t) where changeIndices[s] == i,
    //      for indices i where nums[i] > 0.
    //   2. Scan right-to-left. Maintain a min-heap of nums[i] for committed fast-marks,
    //      and a "mark" counter for available free mark-slots.
    //   3. At first_occ second: push nums[i] to heap, then:
    //        if mark > 0 (have a free slot): mark -= 1 (this second used for set, not free)
    //        else: we need to discard the least-valuable fast-mark (heap.pop()), mark += 1.
    //             (this second itself acts as the free slot for the popped fast-mark's mark)
    //   4. At regular second: mark += 1.
    //   5. Final check: sum(nums) - sum(pq) + n - pq.len() <= mark.
    //      (ops remaining = decrements_for_non_fast_marked + marks_for_all = total_ops - fast_mark_savings)

    let can = |t: usize| -> bool {
      // Find first occurrence of each index i (1-indexed) in changeIndices[0..t) where nums[i]>0
      let mut first_occ = vec![-1i32; n + 1];
      for s in 0..t {
        let idx = change_indices[s] as usize;
        if first_occ[idx] == -1 && nums[idx - 1] > 0 {
          first_occ[idx] = s as i32;
        }
      }
      // Map from position back to index
      let mut pos_to_idx = vec![0usize; t];
      for i in 1..=n {
        if first_occ[i] >= 0 {
          pos_to_idx[first_occ[i] as usize] = i;
        }
      }

      let mut heap: BinaryHeap<Reverse<i64>> = BinaryHeap::new();
      let mut mark: i64 = 0;

      for s in (0..t).rev() {
        let i = pos_to_idx[s];
        if i > 0 {
          // This is the first occurrence of index i; candidate for fast-mark
          heap.push(Reverse(nums[i - 1] as i64));
          if mark > 0 {
            mark -= 1; // this second used as set-op; consume a mark slot
          } else {
            mark += 1; // this second becomes a free slot after popping worst
            heap.pop(); // remove least-valuable fast-mark
          }
        } else {
          mark += 1; // regular free second
        }
      }

      // Remaining ops: for indices NOT in heap (not fast-marked):
      //   sum(nums) - heap_sum (decrements saved by fast-marks)
      //   + n - heap.len() (marks for non-fast-marked indices)
      //   + heap.len() (marks for fast-marked indices, from free seconds)
      //   = n + sum(nums) - heap_sum - heap.len() + heap.len() = n + sum(nums) - heap_sum
      // Wait: fast-marked indices also need 1 mark second (from free pool).
      // Non-fast-marked indices need nums[i] dec-seconds + 1 mark-second.
      // Total free ops needed = (sum_nums - heap_sum) + n
      // These must fit in `mark` free seconds.
      let heap_sum: i64 = heap.iter().map(|&Reverse(v)| v).sum();
      let sum_nums: i64 = nums.iter().map(|&x| x as i64).sum();
      sum_nums - heap_sum + (n - heap.len()) as i64 <= mark
    };

    let mut lo = 1usize;
    let mut hi = m + 1;
    while lo < hi {
      let mid = (lo + hi) / 2;
      if can(mid) { hi = mid; } else { lo = mid + 1; }
    }
    if lo > m { -1 } else { lo as i32 }
  }
}