Figuring out best lower bound for Leetcode #2187. Minimum Time to Complete Trips

Question

The problem:

You are given an array time where time[i] denotes the time taken by the ith bus to complete one trip.

Each bus can make multiple trips successively; that is, the next trip can start immediately after completing the current trip. Also, each bus operates independently; that is, the trips of one bus do not influence the trips of any other bus.

You are also given an integer totalTrips, which denotes the number of trips all buses should make in total. Return the minimum time required to complete at least totalTrips trips.

Let

• $m$ = min(time)
• $N$ = len(time)
• $R$ = totalTrips

I know $mR$ is a good upper bound for the answer. What is a good lower bound?

Assume the best case scenario where all(time[i] = m for i in range(N)). Then, it takes $m$ time units to complete $N$ trips. If fractional trips were allowed to count towards the trip count, then $R$ trips could be completed in $\frac {mR} N$ time units (note this number might not be whole. So, I was wondering if both

• $m \big\lceil \frac R N \big\rceil$
• $\big\lceil \frac {mR} N \big\rceil$

are valid lower bounds and if so, which one gives the higher lower bound (I asked about this separately? I feel like $m \big\lceil \frac R N \big\rceil$ is a valid upper bound and usually $\geq \big\lceil \frac {mR} N \big\rceil$, but can't quite prove it.

My solution passes all tests using either lower bound, but that's not proof that both lower bounds are valid -- maybe one of the lower bounds is invalid and a set of inputs that would make it fail (a counterexample) is not one of the test cases in the test suite.

Solution:

# Binary Search solution
class Solution:
    def minimumTime(self, times: List[int], R: int) -> int:
        def possible(T):
            '''Whether it's possible to do R trips in T time units.'''
            return sum(T // time for time in times) >= R
        m = min(times)
        N = len(times)
        LO = m if R <= N else ceil(m * R / N)   # **lower bound 1**
        # LO = m if R <= N else m * ceil(R / N) # **lower bound 2**
        HI = m * R # upper bound
        # INVARIANT:
        # - It's not possible to do R trips in LO-1 time units
        # - It's possible to do R trips in HI time units
        while LO < HI:
            MID = (LO + HI) >> 1
            if possible(MID):
                HI = MID
            else:
                LO = MID + 1
        # LO == HI
        # It's not possible to do R trips in LO-1 time units
        # It's possible to do R trips in LO time units
        return LO

Answer 1

Given any feasible solution, you can shorten it by speeding up all buses to have trip time $m.$ Having done that, you can speed it up further by having all buses run simultaneously to the extent possible, and by eliminating any deadheading times (transit times between trips for a single bus). That gives overall time $m \big\lceil \frac R N \big\rceil$, so it is indeed a valid lower bound. The inequality $m \big\lceil \frac R N \big\rceil \ge \big\lceil \frac {mR} N \big\rceil$ was proved in an answer to your other (linked) question.