Earliest Time to Finish Enough Independent Trips
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Bus `i` takes `time[i]` units of time to complete one trip. All buses start at time zero, operate independently and immediately begin another trip after completing one. Return the earliest time by which the buses have completed at least `totalTrips` trips in total.
```cpp
class Solution {
public:
long long minimumTime(vector<int>& time, int totalTrips);
};
```
### Examples
**Example 1:**
```text
time = [2,3], totalTrips = 4
Output: 6
Explanation: By time 5 there are 2+1=3 trips; by time 6 there are 3+2=5.
```
**Example 2:**
```text
time = [4,4], totalTrips = 3
Output: 8
Explanation: Two trips finish at time 4 and four at time 8.
```
### Constraints
- `1 <= time.length <= 10^5`.
- `1 <= time[i],totalTrips <= 10^7`.
### Clarifying Questions
Only completed trips count. Exceeding the requested number is permitted.
```hint Inspect the structure
How many trips does one bus finish by a proposed time T?
```
### Reasoning checkpoints
- Count only completed trips while allowing buses to operate concurrently and independently.
- Find the earliest qualifying time, including when several buses finish at the same instant.
- Use safe arithmetic for the largest possible time and aggregate counts.
### Optional extensions
How would delayed bus starting times modify the feasibility count?
Overview: Earliest Time to Finish Enough Independent Trips. Bus i takes time[i] units to finish one trip and immediately starts another. Buses operate independently and all begin at time zero. Return the earliest time at which their total completed trips is at least totalTrips.