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*10⁴
0 <= hens[i], grains[j] <= 10⁹

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.

Python3JavaC++GoTypeScript

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 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;
}

2604. Minimum Time to Eat All Grains 🔒

Description

Solutions

Solution 1: Sorting + Binary Search

Comments