2604. Minimum Time to Eat All Grains

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.

class Solution {
    bool helper(vector<int>& A, vector<int>& B, int m) {
        int j = 0;
        for(int i = 0; i < A.size() and j < B.size(); i++) {
            if(A[i] > B[j]) {
                if(A[i] - B[j] > m) return false;
                int move = max({m - 2 * (A[i] - B[j]), 0, (m - (A[i] - B[j])) / 2});
                while(j < B.size() and B[j] <= A[i] + move) j++;
            } else {
                while(j < B.size() and B[j] <= A[i] + m) j++;
            }
        }
        return j == B.size();
    }
public:
    int minimumTime(vector<int>& A, vector<int>& B) {
        sort(begin(A), end(A));
        sort(begin(B), end(B));
        long long l = 0, r = max(abs(A.front() - B.back()), abs(A.back() - B.front())) * 4ll, res = r;
        while(l <= r) {
            long long m = l + (r - l) / 2;
            bool ok = helper(A,B,m);
            if(ok) {
                res = min(res, m);
                r = m - 1;
            } else l = m + 1;
        }
        return res;
    }
};