Minimum Time to Eat All Grains
HardUpdated: Jan 1, 2025
Practice on:
Problem
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 theminimum time to eat all grains if the hens act optimally.
Examples
Example 1:
Input: hens = [3,6,7], grains = [2,4,7,9]
Output: 2
Explanation:
One of the ways hens eat all grains in 2 seconds is described below:
- The first hen eats the grain at position 2 in 1 second.
- The second hen eats the grain at position 4 in 2 seconds.
- The third hen eats the grains at positions 7 and 9 in 2 seconds.
So, the maximum time needed is 2.
It can be proven that the hens cannot eat all grains before 2 seconds.
Example 2:
Input: hens = [4,6,109,111,213,215], grains = [5,110,214]
Output: 1
Explanation:
One of the ways hens eat all grains in 1 second is described below:
- The first hen eats the grain at position 5 in 1 second.
- The fourth hen eats the grain at position 110 in 1 second.
- The sixth hen eats the grain at position 214 in 1 second.
- The other hens do not move.
So, the maximum time needed is 1.
Constraints:
1 <= hens.length, grains.length <= 2*1040 <= hens[i], grains[j] <= 10^9
Solution
Method 1 – Binary Search + Two Pointers
Intuition
The minimum time is the smallest t such that all grains can be assigned to hens, with each hen able to reach all its assigned grains within t seconds. We can use binary search on t and check feasibility using a greedy two-pointer approach.
Approach
- Sort hens and grains.
- Binary search for the minimum t (from 0 to max distance).
- For each t, use two pointers:
- For each hen, assign as many grains as possible within t seconds.
- Move to next hen when current can't reach next grain within t.
- If all grains are assigned, t is feasible.
- Return the smallest feasible t.
Code
C++
class Solution {
public:
int minimumTime(vector<int>& hens, vector<int>& grains) {
sort(hens.begin(), hens.end());
sort(grains.begin(), grains.end());
int left = 0, right = 1e9, ans = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
int i = 0, j = 0, n = hens.size(), m = grains.size();
while (i < n && j < m) {
int start = j;
while (j < m && abs(grains[j] - hens[i]) <= mid) ++j;
if (start == j) ++i;
}
if (j == m) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
};
Go
func minimumTime(hens, grains []int) int {
sort.Ints(hens)
sort.Ints(grains)
left, right, ans := 0, 1e9, -1
for left <= right {
mid := (left + right) / 2
i, j := 0, 0
for i < len(hens) && j < len(grains) {
start := j
for j < len(grains) && abs(grains[j]-hens[i]) <= mid {
j++
}
if start == j {
i++
}
}
if j == len(grains) {
ans = mid
right = mid - 1
} else {
left = mid + 1
}
}
return ans
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
Java
class Solution {
public int minimumTime(int[] hens, int[] grains) {
Arrays.sort(hens);
Arrays.sort(grains);
int left = 0, right = (int)1e9, ans = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
int i = 0, j = 0, n = hens.length, m = grains.length;
while (i < n && j < m) {
int start = j;
while (j < m && Math.abs(grains[j] - hens[i]) <= mid) ++j;
if (start == j) ++i;
}
if (j == m) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
}
Kotlin
class Solution {
fun minimumTime(hens: IntArray, grains: IntArray): Int {
hens.sort()
grains.sort()
var left = 0
var right = 1_000_000_000
var ans = -1
while (left <= right) {
val mid = left + (right - left) / 2
var i = 0
var j = 0
while (i < hens.size && j < grains.size) {
val start = j
while (j < grains.size && kotlin.math.abs(grains[j] - hens[i]) <= mid) j++
if (start == j) i++
}
if (j == grains.size) {
ans = mid
right = mid - 1
} else {
left = mid + 1
}
}
return ans
}
}
Python
class Solution:
def minimumTime(self, hens: list[int], grains: list[int]) -> int:
hens.sort()
grains.sort()
left, right, ans = 0, 10**9, -1
while left <= right:
mid = (left + right) // 2
i, j = 0, 0
while i < len(hens) and j < len(grains):
start = j
while j < len(grains) and abs(grains[j] - hens[i]) <= mid:
j += 1
if start == j:
i += 1
if j == len(grains):
ans = mid
right = mid - 1
else:
left = mid + 1
return ans
Rust
impl Solution {
pub fn minimum_time(mut hens: Vec<i32>, mut grains: Vec<i32>) -> i32 {
hens.sort();
grains.sort();
let (mut left, mut right, mut ans) = (0, 1_000_000_000, -1);
while left <= right {
let mid = left + (right - left) / 2;
let (mut i, mut j) = (0, 0);
while i < hens.len() && j < grains.len() {
let start = j;
while j < grains.len() && (grains[j] - hens[i]).abs() <= mid {
j += 1;
}
if start == j {
i += 1;
}
}
if j == grains.len() {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
ans
}
}
TypeScript
class Solution {
minimumTime(hens: number[], grains: number[]): number {
hens.sort((a, b) => a - b);
grains.sort((a, b) => a - b);
let left = 0, right = 1e9, ans = -1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
let i = 0, j = 0;
while (i < hens.length && j < grains.length) {
const start = j;
while (j < grains.length && Math.abs(grains[j] - hens[i]) <= mid) j++;
if (start === j) i++;
}
if (j === grains.length) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O((n + m) log D), where n = hens.length, m = grains.length, D = max position difference. - 🧺 Space complexity:
O(1), only pointers and counters are used.