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
Approach 1: Sorting + Binary Search
First, sort the chickens and grains by their position from left to right. Then enumerate the time
For each chicken, we use the pointer
- If
$y \leq x$ , we note that$d = x - y$ . If$d \gt t$ , the current grain cannot be eaten, so directly returnfalse. 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 true, otherwise return false.
Time complexity
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)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;
}
};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 min(a, b int) int {
if a < b {
return a
}
return b
}
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;
}