2187 - Minimum Time to Complete Trips (Medium)

Input: time = [1,2,3], totalTrips = 5
Output: 3
Explanation:
- At time t = 1, the number of trips completed by each bus are [1,0,0].
  The total number of trips completed is 1 + 0 + 0 = 1.
- At time t = 2, the number of trips completed by each bus are [2,1,0].
  The total number of trips completed is 2 + 1 + 0 = 3.
- At time t = 3, the number of trips completed by each bus are [3,1,1].
  The total number of trips completed is 3 + 1 + 1 = 5.
So the minimum time needed for all buses to complete at least 5 trips is 3.

Input: time = [2], totalTrips = 1
Output: 2
Explanation:
There is only one bus, and it will complete its first trip at t = 2.
So the minimum time needed to complete 1 trip is 2.

def minimumTime(self, time: List[int], totalTrips: int) -> int:

        #checker function
        def check(x):
            nonlocal totalTrips

            #keep track of how many trips we have visited
            trips = 0
            for t in time:

                #we can visit x//t trips (rounded down)
                trips += x // t

                #return true when we have fulfilled the requirement
                if(trips >= totalTrips):
                    return True
            #return false if the requirement has not been fulfilled
            return False

        #standard binary search setting of left pointer and right pointer
        lp = 0
        rp = time[0] * totalTrips + 1
        res = rp

        while(lp <= rp):

            #standard middle point of binary search
            mid = (lp+rp) // 2

            #check if the middle point satisfies the requirement
            if(check(mid)):
                #if it satisfies, update the result
                #also decrease the right pointer to look at smaller times
                res = mid
                rp = mid - 1
            else:
                #increase the left pointer to look at bigger times otherwise
                lp = mid + 1

        return res

class Solution {
public:
    long long minimumTime(vector<int>& time, int totalTrips) {
        long long l = *min_element(time.begin(), time.end());
        long long r = accumulate(time.begin(), time.end(), 0LL) * totalTrips;
        while (l < r) {
            long long m = l + (r - l) / 2, trips = 0;
            for (auto x : time) trips += (m / x);
            if (trips < totalTrips) l = m + 1;
            else r = m;
        }
        return l;
    }
};