2332. The Latest Time to Catch a Bus

You are given a 0-indexed integer array buses of length n, where buses[i] represents the departure time of the ith bus. You are also given a 0-indexed integer array passengers of length m, where passengers[j] represents the arrival time of the jth passenger. All bus departure times are unique. All passenger arrival times are unique.

You are given an integer capacity, which represents the maximum number of passengers that can get on each bus.

The passengers will get on the next available bus. You can get on a bus that will depart at x minutes if you arrive at y minutes where y <= x, and the bus is not full. Passengers with the earliest arrival times get on the bus first.

Return the latest time you may arrive at the bus station to catch a bus. You cannot arrive at the same time as another passenger.

Note: The arrays buses and passengers are not necessarily sorted.

class Solution {
public:
    int latestTimeCatchTheBus(vector<int>& A, vector<int>& B, int cap) {
        int res = 0, i = 0, j = 0, n = A.size(), m = B.size(), now = 0;
        sort(begin(A), end(A));
        sort(begin(B), end(B));
        while(i < n) {
            while(j < m and B[j] <= A[i]) {
                now++;
                if(now <= cap) {
                    if(j and B[j] - 1 != B[j-1]) res = max(res, B[j]-1);
                    else if(j == 0) res = B[j]-1;
                    if((j + 1 == m or B[j] + 1 != B[j+1]) and B[j] + 1 <= A[i]) res = max(res, B[j] + 1);
                }
                if(now < cap) {
                    if((j + 1 == m or B[j] + 1 != B[j+1]) and B[j] + 1 <= A[i]) res = max(res, B[j] + 1);
                }
                long long remianbus = n - i;
                
                if(remianbus * cap - now >= 0) {
                    if(j and B[j-1] != B[j] - 1) res = max(res,B[j] - 1);
                    else if(j == 0) res = max(res,B[j] - 1);
                    if((j + 1 == m or B[j] + 1 != B[j+1]) and B[j] + 1 <= A[i]) res = max(res, B[j] + 1);
                }
                if(remianbus * cap - now > 0) {
                    if((j + 1 == m or B[j] + 1 != B[j+1]) and B[j] + 1 <= A[i]) res = max(res, B[j] + 1);
                }
                j++;
            }
            int mi = min(cap, now);
            if(mi < cap and (j and B[j-1] != A[i])) res = max(res,A[i]);
            else if(j == 0) res = A[i];
            now -= mi;
            i++;
        }
        return res;
    }
};