Minimum Time to Complete Trips

Master this topic with zero to advance depth.

Minimum Time to Complete Trips

You are given an array time where time[i] denotes the time taken by the $i$ -th bus to complete one trip. Return the minimum time required for all buses to complete at least totalTrips trips.

Medium

Examples

Input: time = [1,2,3], totalTrips = 5
Output: 3

Approach 1

Level I: Brute Force

Intuition

Iterate from time $T=1$ upwards and check if the total trips $\\sum \\lfloor T / time[i] \\rfloor$ reaches totalTrips.

⏱ $O(MinTime \\cdot TotalTrips)$💾 $O(1)$

Detailed Dry Run

time = [1,2,3], totalTrips = 5

T=1: trips = 1/1 + 1/2 + 1/3 = 1 < 5
T=2: trips = 2/1 + 2/2 + 2/3 = 3 < 5
T=3: trips = 3/1 + 3/2 + 3/3 = 5 >= 5. Return 3.

java

class Solution {
    public long minimumTime(int[] time, int totalTrips) {
        long t = 1;
        while (true) {
            long trips = 0;
            for (int b : time) trips += t / b;
            if (trips >= totalTrips) return t;
            t++;
        }
    }
}

Approach 2

Level III: Optimal (Binary Search on Answer)

Intuition

The number of trips is monotone relative to time. We can binary search the answer range [1, min(time) * totalTrips].

⏱ $O(N \\cdot \\log(MinTime \\cdot TotalTrips))$💾 $O(1)$

Detailed Dry Run

Step	L	R	Mid	Trips	Decision
1	1	5	3	5	R = 3
2	1	3	2	3	L = 3
Exit	-	-	-	-	Return 3

java

class Solution {
    public long minimumTime(int[] time, int totalTrips) {
        long l = 1, r = (long)time[0] * totalTrips;
        for (int t : time) r = Math.min(r, (long)t * totalTrips);
        while (l < r) {
            long m = l + (r - l) / 2, trips = 0;
            for (int t : time) trips += m / t;
            if (trips >= totalTrips) r = m; else l = m + 1;
        }
        return l;
    }
}

← Previous QuestionFind K-th Smallest Pair Distance

Next Question →Maximum Running Time of N Computers

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.