Skip to content

2604. Minimum Time to Eat All Grains 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(\texttt{sort})$
 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
38
39
40
41
42
43
44
45
46
47
class Solution {
 public:
  int minimumTime(vector<int>& hens, vector<int>& grains) {
    sort(hens.begin(), hens.end());
    sort(grains.begin(), grains.end());

    const int maxPosition = max(*max_element(hens.begin(), hens.end()),
                                *max_element(grains.begin(), grains.end()));
    const int minPosition = min(*min_element(hens.begin(), hens.end()),
                                *min_element(grains.begin(), grains.end()));
    int l = 0;
    int r = 1.5 * (maxPosition - minPosition);

    while (l < r) {
      const int m = (l + static_cast<long>(r)) / 2;
      if (canEat(hens, grains, m))
        r = m;
      else
        l = m + 1;
    }

    return l;
  }

 private:
  // Returns true if `hens` can eat all `grains` within `time`.
  bool canEat(const vector<int>& hens, const vector<int>& grains, int time) {
    int i = 0;  // grains[i] := next grain to be ate
    for (const int hen : hens) {
      int moves = time;
      if (grains[i] < hen) {
        // `hen` needs go back to eat `grains[i]`.
        const int leftMoves = hen - grains[i];
        if (leftMoves > time)
          return false;
        const int leftThenRight = time - 2 * leftMoves;
        const int rightThenLeft = (time - leftMoves) / 2;
        moves = max({0, leftThenRight, rightThenLeft});
      }
      i = upper_bound(grains.begin(), grains.end(), hen + moves) -
          grains.begin();
      if (i == grains.size())
        return true;
    }
    return false;
  }
};

 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
  public int minimumTime(int[] hens, int[] grains) {
    Arrays.sort(hens);
    Arrays.sort(grains);

    final int maxPosition = Math.max(Arrays.stream(hens).max().getAsInt(), //
                                     Arrays.stream(grains).max().getAsInt());
    final int minPosition = Math.min(Arrays.stream(hens).min().getAsInt(), //
                                     Arrays.stream(grains).min().getAsInt());
    int l = 0;
    int r = (int) (1.5 * (maxPosition - minPosition));

    while (l < r) {
      final int m = (int) ((l + (long) r) / 2);
      if (canEat(hens, grains, m))
        r = m;
      else
        l = m + 1;
    }

    return (int) l;
  }

  // Returns true if `hens` can eat all `grains` within `time`.
  private boolean canEat(int[] hens, int[] grains, int time) {
    int i = 0; // grains[i] := next grain to be ate
    for (final int hen : hens) {
      int rightMoves = time;
      if (grains[i] < hen) {
        // `hen` needs go back to eat `grains[i]`.
        final int leftMoves = hen - grains[i];
        if (leftMoves > time)
          return false;
        final int leftThenRight = time - 2 * leftMoves;
        final int rightThenLeft = (time - leftMoves) / 2;
        rightMoves = Math.max(0, Math.max(leftThenRight, rightThenLeft));
      }
      i = firstGreater(grains, hen + rightMoves);
      if (i == grains.length)
        return true;
    }
    return false;
  }

  private int firstGreater(int[] A, int target) {
    int l = 0;
    int r = A.length;
    while (l < r) {
      final int m = (l + r) / 2;
      if (A[m] > target)
        r = m;
      else
        l = m + 1;
    }
    return l;
  }
}

 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
class Solution:
  def minimumTime(self, hens: List[int], grains: List[int]) -> int:
    hens.sort()
    grains.sort()

    # Returns true if `hens` can eat all `grains` within `time`.
    def canEat(time: int) -> bool:
      i = 0  # grains[i] := next grain to be ate
      for hen in hens:
        rightMoves = time
        if grains[i] < hen:
          # `hen` needs go back to eat `grains[i]`.
          leftMoves = hen - grains[i]
          if leftMoves > time:
            return False
          leftThenRight = time - 2 * leftMoves
          rightThenLeft = (time - leftMoves) // 2
          rightMoves = max(0, leftThenRight, rightThenLeft)
        i = bisect.bisect_right(grains, hen + rightMoves)
        if i == len(grains):
          return True
      return False

    maxMoves = int(1.5 * (max(hens + grains) - min(hens + grains)))
    return bisect.bisect_left(range(maxMoves), True, key=lambda m: canEat(m))