Minimum Time to Complete Trips Problem

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

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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:

1
2
3
4
5
6
7

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.

Solution

Method 1 – Feasibility Check with Binary Search

Intuition

We want to find the minimum time t such that the total number of trips completed by all buses in t time is at least totalTrips. For a given t, the number of trips a bus with time[i] can make is t // time[i]. We can use binary search to find the smallest t that works.

Approach

  1. Set low to 1 and high to max(time) * totalTrips (worst case: slowest bus does all trips).
  2. For each mid value, calculate total trips all buses can make in mid time.
  3. If total trips >= totalTrips, try a smaller time; else, try a larger time.
  4. The answer is the smallest time found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    long long minimumTime(vector<int>& time, int totalTrips) {
        long long l = 1, r = 1LL * *max_element(time.begin(), time.end()) * totalTrips, ans = r;
        while (l <= r) {
            long long m = l + (r - l) / 2, trips = 0;
            for (int t : time) trips += m / t;
            if (trips >= totalTrips) ans = m, r = m - 1;
            else l = m + 1;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

func minimumTime(time []int, totalTrips int) int64 {
    l, r := int64(1), int64(time[0])*int64(totalTrips)
    for _, t := range time {
        if int64(t)*int64(totalTrips) > r {
            r = int64(t) * int64(totalTrips)
        }
    }
    var ans int64 = r
    for l <= r {
        m := l + (r-l)/2
        trips := int64(0)
        for _, t := range time {
            trips += m / int64(t)
        }
        if trips >= int64(totalTrips) {
            ans = m
            r = m - 1
        } else {
            l = m + 1
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public long minimumTime(int[] time, int totalTrips) {
        long l = 1, r = (long) Arrays.stream(time).max().getAsInt() * totalTrips, ans = r;
        while (l <= r) {
            long m = l + (r - l) / 2, trips = 0;
            for (int t : time) trips += m / t;
            if (trips >= totalTrips) {
                ans = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun minimumTime(time: IntArray, totalTrips: Int): Long {
        var l = 1L
        var r = time.maxOrNull()!!.toLong() * totalTrips
        var ans = r
        while (l <= r) {
            val m = l + (r - l) / 2
            var trips = 0L
            for (t in time) trips += m / t
            if (trips >= totalTrips) {
                ans = m
                r = m - 1
            } else {
                l = m + 1
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def minimumTime(self, time: list[int], totalTrips: int) -> int:
        l, r = 1, max(time) * totalTrips
        ans = r
        while l <= r:
            m = (l + r) // 2
            trips = sum(m // t for t in time)
            if trips >= totalTrips:
                ans = m
                r = m - 1
            else:
                l = m + 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn minimum_time(time: Vec<i32>, total_trips: i32) -> i64 {
        let (mut l, mut r) = (1i64, *time.iter().max().unwrap() as i64 * total_trips as i64);
        let mut ans = r;
        while l <= r {
            let m = l + (r - l) / 2;
            let trips = time.iter().map(|&t| m / t as i64).sum::<i64>();
            if trips >= total_trips as i64 {
                ans = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    minimumTime(time: number[], totalTrips: number): number {
        let l = 1, r = Math.max(...time) * totalTrips, ans = r;
        while (l <= r) {
            let m = Math.floor((l + r) / 2), trips = 0;
            for (let t of time) trips += Math.floor(m / t);
            if (trips >= totalTrips) {
                ans = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log(max(time) * totalTrips)), where n is the number of buses. Each binary search step checks all buses.
  • 🧺 Space complexity: O(1), only constant extra space is used.