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*104
  • 0 <= 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 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;
    }
    
    

All Problems

All Solutions