[LeetCode] 2187. Minimum Time to Complete Trips (Medium/Python)

Minimum Time to Complete Trips - LeetCode

Above is the link to the problem.

 

Problem

You are given an array "time" where "time[i]" denotes the time taken by the i th 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 don't 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 for all buses to complete at least totalTrips.

 

Example 

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.

 

Code

The time complexity of the code is lower than O(nlogn) to avoid the time exceeding issue.

So we have to use a binary search algorithm to find the minimum time.

 

This code gets the top 11.93% of time complexity and uses 28.8MB of memory.