2604. Minimum Time to Eat All Grains

Posted on Edited on In

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:

1
2
3
4
5
6
7
8
9
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:

1
2
3
4
5
6
7
8
9
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^4
  • 0 <= hens[i], grains[j] <= 10^9

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    int minimumTime(vector<int>& hens, vector<int>& grains) {
        ranges::sort(hens);
        ranges::sort(grains);
        unordered_set<int> henset(hens.begin(), hens.end());
        int left = -1, right = 2e9 + 1;
        while (left + 1 < right) {
            int mid = (right - left) / 2 + left;
            if (check(mid, hens, grains)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }

    bool check(long time, vector<int>& hens, vector<int>& grains) {
        int n = grains.size(), r = 0;
        for (int hen : hens) {
            long budget = time;
            if (hen > grains[r]) {
                if (hen - grains[r] > time) return false;
                long diff = hen - grains[r];
                budget = max(budget - 2 * diff, (budget - diff) / 2);
            }
            while (r < n && grains[r] - hen <= budget) {
                r++;
            }
            if (r == n) {
                return true;
            }
        }
        return false;
    }
};