 # Race 282 of the week: Minimum time to complete the journey

Posted on May 27, 2023, 3:15 p.m. by Ojas Garg
Category: The front end

"Offer comes, ask friends to take it! I am participating in the 2022 Spring Recruit Punch card campaign. Click here for more details."

## I. Problem description

You are given an array of time, where time[I] represents how long it takes the ith bus to complete a trip.

Each bus can make multiple trips in a row, which means that a bus can start its next trip as soon as it completes its current trip. Each bus operates independently, which means that multiple buses can operate at the same time without affecting each other.

I'm going to give you an integer totalTrips, which is the total number of trips that all buses have to make. Return the minimum time required to complete at least totalTrips.

Minimum time to complete the journey.

## Two, the title requirements

### The sample

``Input: time = [1,2,3], totalTrips = 5 Output: 3 Explanation: - time t = 1, the number of trips completed by each bus is [1,0,0] respectively. The total number of completed trips is 1 + 0 + 0 = 1. - at time t = 2, the number of journeys completed by each bus is [2,1,0]. The total number of completed trips is 2 + 1 + 0 = 3. - at time t = 3, the number of journeys completed by each bus is [3,1,1]. The total number of completed trips is 3 + 1 + 1 = 5. So the minimum time to complete at least 5 trips is 3.Copy the code``

### inspection

``1. Binary search 2. You are advised to use 20 to 40 minutes for binary searchCopy the code``

## Third, problem analysis So the way I thought about it at the beginning is, time t is slowly increasing. The number of trips per bus can be directly used in time/time spent, just return the minimum time. This is also the simplest algorithm, but unfortunately timed out, you can't optimize it. Later after the end of the problem to see the big guy's solution, found that this problem can be solved with dichotomous algorithm, want to break the head did not think: Here are the steps:

• The minimum time to complete the journey is 0 (no walking required) and the maximum time is for the fastest bus to complete the journey itself
• Left = 0, right = time*totalTrips, mid=left+(right-left)/2
• Mid represents the total amount of time currently spent. We need to calculate the number of completed journeys in mid, sum
• Sum =totalTrips, right=mid
• Sum
• Exit the loop and return left

## Four, coding implementation

``````class Solution {
public:
long long minimumTime(vectorint time, int totalTrips) {
long long int i,sum,n=time.size(),left,right,mid;// Initialize related data
sort(time.begin(),time.end());// Sort from smallest to largest
left=0,right=1L* time*totalTrips;// Left edge right edge
while(leftright)// loop judgment
{
mid=left+(right-left)/2;// The median value is mid
sum=0;// The number of trips is initialized
for(i=0; in; i++)// The cycle of time it takes a bus to complete a journey
{
if(time[i]mid)
break;
sum+=mid/time[i];// Find the number of journeys
}
if(sum=totalTrips)
right=mid;// Zoom out to the left
else
left=mid+1;// Zoom out to the right
}
return left;// Output the result}};Copy the code``````

## V. Test results  Search