Minimum time to eat all grains

Array Two Pointers Binary Search Sorting

40.7% acceptance

Mar 31, 2026

There are n hens and m grains on a line. You are given the initial positions of the hens and the grains in two integer arrays hens and grains of size n and m respectively. Any hen can eat a grain if they are on the same position. The time taken for this is negligible. One hen can also eat multiple grains. In 1 second, a hen can move right or left by 1 unit. The hens can move simultaneously and independently of each other. Return the minimum time to eat all grains if the hens act optimally.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_time(mut hens: Vec<i32>, mut grains: Vec<i32>) -> i32 {
    hens.sort();
    grains.sort();
    let can = |t: i64| -> bool {
      let mut g = 0usize;
      for &h in &hens {
        if g >= grains.len() { return true; }
        let h = h as i64;
        let gl = grains[g] as i64;
        if gl > h + t { continue; }
        if gl >= h {
          while g < grains.len() && grains[g] as i64 <= h + t {
            g += 1;
          }
        } else {
          let left_dist = h - gl;
          if left_dist > t { continue; }
          let right_reach = (h + 0i64.max(t - 2 * left_dist))
            .max(h + 0i64.max((t - left_dist) / 2));
          while g < grains.len() && grains[g] as i64 <= right_reach {
            g += 1;
          }
        }
      }
      g >= grains.len()
    };
    let mut lo: i64 = 0;
    let mut hi: i64 = 2_000_000_000;
    while lo < hi {
      let mid = lo + (hi - lo) / 2;
      if can(mid) { hi = mid; } else { lo = mid + 1; }
    }
    lo as i32
  }
}