# Minimum Time to Complete Trips
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-time-to-complete-trips)
Canonical: https://scaleengineer.com/dsa/problems/minimum-time-to-complete-trips
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [Amadeus](https://scaleengineer.com/companies/amadeus)
---
## 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_.

**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 = [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 <= 105`
* `1 <= time[i], totalTrips <= 107`

# Approaches
## Brute Force (Linear Search)
This approach involves checking every possible time value, starting from 1, and incrementing it one by one. For each time `t`, we calculate the total number of trips that all buses can complete. The first time `t` for which the total trips is greater than or equal to `totalTrips` is the minimum time required.
**Time:** O(Ans * N), where `Ans` is the minimum time required and `N` is the number of buses. In the worst case, `Ans` can be up to `10^7 * 10^7 = 10^14`, which is computationally infeasible. · **Space:** O(1), as we only use a few variables to store the current time and total trips.
**Pros:** Simple to understand and straightforward to implement.
**Cons:** Extremely inefficient due to its linear scan of the time domain.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints as the answer can be very large.
### Explanation
The algorithm iterates through time, starting from `t = 1`. In each iteration, it calculates the total number of trips possible by that time.

To calculate the total trips for a given time `t`, we iterate through the `time` array. For each bus `i` with trip time `time[i]`, the number of trips it can complete is `t / time[i]`. We sum these values for all buses.

If the calculated total trips is at least `totalTrips`, we have found our answer, and we return the current time `t`.

This process continues until the condition is met. However, the maximum possible answer can be very large (up to `10^14`), making this approach too slow for the given constraints.

```java
class Solution {
    public long minimumTime(int[] time, int totalTrips) {
        // This approach is too slow and will time out.
        long currentTime = 1;
        while (true) {
            long tripsCompleted = 0;
            for (int t : time) {
                // Using long for currentTime to avoid overflow issues, though
                // this loop will time out long before overflow becomes a problem.
                tripsCompleted += currentTime / t;
            }
            if (tripsCompleted >= totalTrips) {
                return currentTime;
            }
            currentTime++;
        }
    }
}
```
### Algorithm
- Initialize a variable `currentTime` to 1.
- Start an infinite loop.
- Inside the loop, initialize `tripsCompleted` to 0.
- Iterate through each `busTime` in the `time` array.
- For each `busTime`, calculate the trips completed by `currentTime` as `currentTime / busTime` and add it to `tripsCompleted`.
- After checking all buses, if `tripsCompleted` is greater than or equal to `totalTrips`, then `currentTime` is the minimum time. Return `currentTime`.
- If not, increment `currentTime` and continue the loop.

## Binary Search on the Answer
A much more efficient approach is to use binary search on the answer. The key observation is that the total number of trips completed is a monotonically increasing function of time. If we can complete `totalTrips` in time `t`, we can also complete them in any time `t' > t`. This property allows us to binary search for the minimum time `t`.
**Time:** O(N * log(K)), where `N` is the number of buses and `K` is the search range for time (from 1 to `min(time) * totalTrips`). The `log(K)` factor comes from the binary search, and the `N` factor comes from calculating the total trips in each step of the search. · **Space:** O(1), as we only use a few variables for the binary search boundaries and the result.
**Pros:** Highly efficient and optimal for the given constraints.; Guaranteed to find the correct minimum time by effectively narrowing down the search space.
**Cons:** Slightly more complex to conceptualize than a linear search.; Requires careful handling of `long` data types to avoid integer overflow in time calculations.
### Explanation
We first define a search space for the possible answer (time). The lower bound can be `1`. A reasonable upper bound is the time it would take for the fastest bus to complete all the trips by itself, which is `min(time) * totalTrips`. Since this value can be very large, we must use `long` to avoid integer overflow.

We then perform a binary search within this range `[low, high]`.

In each step of the binary search, we take the middle time `mid` and check if it's possible to complete `totalTrips` within this time. We do this by creating a helper function `canComplete(mid)` which calculates the total trips `sum(mid / time[i])` and checks if it's `>= totalTrips`.

- If `canComplete(mid)` is true, it means `mid` is a potential answer, and there might be an even smaller time that works. So, we record `mid` as a possible answer and shrink our search space to the left half: `high = mid - 1`.
- If `canComplete(mid)` is false, `mid` is too small. We need more time, so we search in the right half: `low = mid + 1`.

The search continues until `low` exceeds `high`. The last valid time we found is the minimum time.

```java
class Solution {
    public long minimumTime(int[] time, int totalTrips) {
        long low = 1;
        long minTime = Long.MAX_VALUE;
        for (int t : time) {
            minTime = Math.min(minTime, t);
        }
        long high = minTime * totalTrips; // A reasonable upper bound
        long ans = high;

        while (low <= high) {
            long mid = low + (high - low) / 2;
            if (isPossible(time, totalTrips, mid)) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }

    private boolean isPossible(int[] time, int totalTrips, long givenTime) {
        long tripsCompleted = 0;
        for (int t : time) {
            tripsCompleted += givenTime / t;
            // An early exit optimization: if we've already met the goal,
            // no need to calculate further.
            if (tripsCompleted >= totalTrips) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
- Determine the search range for the time. The lower bound `low` is 1. A good upper bound `high` is the time taken by the fastest bus to complete all trips alone, i.e., `min(time) * totalTrips`. Use `long` for these variables to prevent overflow.
- Initialize a variable `ans` to `high` to store the minimum time found so far.
- While `low <= high`:
  - Calculate the midpoint `mid = low + (high - low) / 2`.
  - Check if it's possible to complete `totalTrips` within `mid` time. This is done by calculating `trips = sum(mid / t)` for each `t` in `time`.
  - If `trips >= totalTrips`:
    - `mid` is a valid time. It might be the minimum, so we store it: `ans = mid`.
    - Try to find an even smaller time by searching in the left half: `high = mid - 1`.
  - Else (`trips < totalTrips`):
    - `mid` is not enough time. We need more time, so search in the right half: `low = mid + 1`.
- After the loop terminates, `ans` will hold the minimum time required.

# Solutions
### Java

```java
class Solution {
public
  long minimumTime(int[] time, int totalTrips) {
    int mi = time[0];
    for (int v : time) {
      mi = Math.min(mi, v);
    }
    long left = 1, right = (long)mi * totalTrips;
    while (left < right) {
      long cnt = 0;
      long mid = (left + right) >> 1;
      for (int v : time) {
        cnt += mid / v;
      }
      if (cnt >= totalTrips) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long minimumTime(vector<int> &time, int totalTrips) {
    int mi = *min_element(time.begin(), time.end());
    long long left = 1, right = (long long)mi * totalTrips;
    while (left < right) {
      long long cnt = 0;
      long long mid = (left + right) >> 1;
      for (int v : time)
        cnt += mid / v;
      if (cnt >= totalTrips)
        right = mid;
      else
        left = mid + 1;
    }
    return left;
  }
};

```

### Python

```python
class Solution:
    def minimumTime(self, time: List[int], totalTrips: int) -> int: mx = min(time) * totalTrips return bisect_left(range(mx), totalTrips, key=lambda x: sum(x // v for v in time))

```