Minimum Time to Complete Trips

Problem Statement:-

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 for all buses to complete at least totalTrips trips.

Link: https://leetcode.com/problems/minimum-time-to-complete-trips/description/

Problem Explanation with examples:-

Example 1

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.

Example 2

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

Example 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.

Constraints

1 <= time.length <= 10^5
1 <= time[i], totalTrips <= 10^7

Intuition:-

• The lowest possible answer can be 1 when totalTrips = 1 and the bus with the shortest time takes only 1 unit of time

• The highest possible answer can be the shortest time * totalTrips when all the buses take the longest time

• Now thinking of bounds, what is the best way to find the answer?

• We can use binary search to find the answer

• In every iteration, we find a middle point and check if the number of trips in that time is greater than or equal to the total trips

• Accordingly, we update the bounds

• Finally, we return the left bound as it will be the lowest possible time to complete all the trips

• Another approach could also be storing all the times in a map and then keep incrementing a counter from 0 and parallelly checking how many factors of the current counter are present in the map and increasing trips by that factor count and then checking if trips >= totalTrips and return the counter if true. But this approach will take more time as we will have to iterate over the map for every counter value.

Solution:-

• First, we can see that the answer is in the range of [1, min(time)*totalTrips]

• Initialize l = 1, r = min(time)*totalTrips

• Then run a while loop, while l < r

• In the while loop, calculate mid = (l+r)//2

• Then take a variable trips_in_m = 0 to count the number of trips in m minutes

• For each time in the time array, we can calculate the number of trips in m minutes by m//time and add it to trips_in_m

• Finally, compare trips_in_m with totalTrips, if trips_in_m >= totalTrips, we can set r = m, otherwise, we can set l = m+1

• After the while loop, we can return l

Code:-

JAVA Solution

class Solution {
    public int minimumTime(int[] time, int totalTrips) {
        int l = 1;
        int r = Arrays.stream(time).min().orElse(0) * totalTrips;

        while (l < r) {
            int m = (l + r) / 2;
            int trips_in_m = 0;
            for (int i : time) {
                trips_in_m += m / i;
            }
            if (trips_in_m >= totalTrips) {
                r = m;
            } else {
                l = m + 1;
            }
        }

        return l;
    }
}

Python Solution

class Solution:
    def minimumTime(self, time: List[int], totalTrips: int) -> int:
        l = 1
        r = min(time)*totalTrips

        while l < r:
            m = (l+r)//2
            trips_in_m = 0
            for i in time:
                trips_in_m += (m//i)
            if trips_in_m >= totalTrips:
                r = m
            else:
                l = m+1

        return l

Complexity Analysis:-

TIME:-

Time complexity is O(NlogN) as for each while loop iteration, we need to iterate through the time list to calculate the number of trips in m and the while loop will run logN times

SPACE:-

Space complexity is O(1), as we only need to store the left, right and middle index and the number of trips in m

References:-

• Binary Search

Connect with me:-

• Twitter

• Github

• LinkedIn