Welcome to Subscribe On Youtube
2604. Minimum Time to Eat All Grains
Description
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.
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] <= 109
Solutions
Solution 1: Sorting + Binary Search
First, sort the chickens and grains by their position from left to right. Then enumerate the time $t$ using binary search to find the smallest $t$ such that all the grains can be eaten up in $t$ seconds.
For each chicken, we use the pointer $j$ to point to the leftmost grain that has not been eaten, and the current position of the chicken is $x$ and the position of the grain is $y$. There are the following cases:
- If $y \leq x$, we note that $d = x - y$. If $d \gt t$, the current grain cannot be eaten, so directly return
false. Otherwise, move the pointer $j$ to the right until $j=m$ or $grains[j] \gt x$. At this point, we need to check whether the chicken can eat the grain pointed to by $j$. If it can, continue to move the pointer $j$ to the right until $j=m$ or $min(d, grains[j] - x) + grains[j] - y \gt t$. - If $y \lt x$, move the pointer $j$ to the right until $j=m$ or $grains[j] - x \gt t$.
If $j=m$, it means that all the grains have been eaten, return true, otherwise return false.
Time complexity $O(n \times \log n + m \times \log m + (m + n) \times \log U)$, space complexity $O(\log m + \log n)$. $n$ and $m$ are the number of chickens and grains respectively, and $U$ is the maximum value of all the chicken and grain positions.
-
class Solution { private int[] hens; private int[] grains; private int m; public int minimumTime(int[] hens, int[] grains) { m = grains.length; this.hens = hens; this.grains = grains; Arrays.sort(hens); Arrays.sort(grains); int l = 0; int r = Math.abs(hens[0] - grains[0]) + grains[m - 1] - grains[0]; while (l < r) { int mid = (l + r) >> 1; if (check(mid)) { r = mid; } else { l = mid + 1; } } return l; } private boolean check(int t) { int j = 0; for (int x : hens) { if (j == m) { return true; } int y = grains[j]; if (y <= x) { int d = x - y; if (d > t) { return false; } while (j < m && grains[j] <= x) { ++j; } while (j < m && Math.min(d, grains[j] - x) + grains[j] - y <= t) { ++j; } } else { while (j < m && grains[j] - x <= t) { ++j; } } } return j == m; } } -
class Solution { public: int minimumTime(vector<int>& hens, vector<int>& grains) { int m = grains.size(); sort(hens.begin(), hens.end()); sort(grains.begin(), grains.end()); int l = 0; int r = abs(hens[0] - grains[0]) + grains[m - 1] - grains[0]; auto check = [&](int t) -> bool { int j = 0; for (int x : hens) { if (j == m) { return true; } int y = grains[j]; if (y <= x) { int d = x - y; if (d > t) { return false; } while (j < m && grains[j] <= x) { ++j; } while (j < m && min(d, grains[j] - x) + grains[j] - y <= t) { ++j; } } else { while (j < m && grains[j] - x <= t) { ++j; } } } return j == m; }; while (l < r) { int mid = (l + r) >> 1; if (check(mid)) { r = mid; } else { l = mid + 1; } } return l; } }; -
class Solution: def minimumTime(self, hens: List[int], grains: List[int]) -> int: def check(t): j = 0 for x in hens: if j == m: return True y = grains[j] if y <= x: d = x - y if d > t: return False while j < m and grains[j] <= x: j += 1 while j < m and min(d, grains[j] - x) + grains[j] - y <= t: j += 1 else: while j < m and grains[j] - x <= t: j += 1 return j == m hens.sort() grains.sort() m = len(grains) r = abs(hens[0] - grains[0]) + grains[-1] - grains[0] + 1 return bisect_left(range(r), True, key=check) -
func minimumTime(hens []int, grains []int) int { sort.Ints(hens) sort.Ints(grains) m := len(grains) l, r := 0, abs(hens[0]-grains[0])+grains[m-1]-grains[0] check := func(t int) bool { j := 0 for _, x := range hens { if j == m { return true } y := grains[j] if y <= x { d := x - y if d > t { return false } for j < m && grains[j] <= x { j++ } for j < m && min(d, grains[j]-x)+grains[j]-y <= t { j++ } } else { for j < m && grains[j]-x <= t { j++ } } } return j == m } for l < r { mid := (l + r) >> 1 if check(mid) { r = mid } else { l = mid + 1 } } return l } func abs(x int) int { if x < 0 { return -x } return x } -
function minimumTime(hens: number[], grains: number[]): number { hens.sort((a, b) => a - b); grains.sort((a, b) => a - b); const m = grains.length; let l = 0; let r = Math.abs(hens[0] - grains[0]) + grains[m - 1] - grains[0] + 1; const check = (t: number): boolean => { let j = 0; for (const x of hens) { if (j === m) { return true; } const y = grains[j]; if (y <= x) { const d = x - y; if (d > t) { return false; } while (j < m && grains[j] <= x) { ++j; } while (j < m && Math.min(d, grains[j] - x) + grains[j] - y <= t) { ++j; } } else { while (j < m && grains[j] - x <= t) { ++j; } } } return j === m; }; while (l < r) { const mid = (l + r) >> 1; if (check(mid)) { r = mid; } else { l = mid + 1; } } return l; }