Maximum number of tasks you can assign

Array Two Pointers Binary Search Greedy Queue Sorting Monotonic Queue

50.2% acceptance

Feb 25, 2026

1091

You have n tasks and m workers. Each task has a strength requirement stored in a 0-indexed integer array tasks, with the ith task requiring tasks[i] strength to complete. The strength of each worker is stored in a 0-indexed integer array workers, with the jth worker having workers[j] strength. Each worker can only be assigned to a single task and must have a strength greater than or equal to the task's strength requirement (i.e., workers[j] >= tasks[i]). Additionally, you have pills magical pills that will increase a worker's strength by strength. You can decide which workers receive the magical pills, however, you may only give each worker at most one magical pill. Given the 0-indexed integer arrays tasks and workers and the integers pills and strength, return the maximum number of tasks that can be completed.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_task_assign(mut tasks: Vec<i32>, mut workers: Vec<i32>, pills: i32, strength: i32) -> i32 {
    tasks.sort_unstable();
    workers.sort_unstable();
    let m = workers.len();
    let n = tasks.len();

    let can_do = |k: usize| -> bool {
      if k > m { return false; }
      use std::collections::BTreeMap;
      let mut wmap: BTreeMap<i32, usize> = BTreeMap::new();
      for &w in &workers[m - k..] {
        *wmap.entry(w).or_insert(0) += 1;
      }
      let mut rem_pills = pills;
      for &t in tasks[..k].iter().rev() {
        if let Some((&w, _)) = wmap.range(t..).next() {
          let cnt = wmap.get_mut(&w).unwrap();
          *cnt -= 1;
          if *cnt == 0 { wmap.remove(&w); }
        } else if rem_pills > 0 {
          let needed = t - strength;
          if let Some((&w, _)) = wmap.range(needed..).next() {
            rem_pills -= 1;
            let cnt = wmap.get_mut(&w).unwrap();
            *cnt -= 1;
            if *cnt == 0 { wmap.remove(&w); }
          } else {
            return false;
          }
        } else {
          return false;
        }
      }
      true
    };

    let mut lo = 0usize;
    let mut hi = n.min(m);
    while lo < hi {
      let mid = lo + (hi - lo + 1) / 2;
      if can_do(mid) { lo = mid; } else { hi = mid - 1; }
    }
    lo as i32
  }
}