370. Trips Deadline
A city runs several buses on the same route. Bus i needs times[i] minutes for one complete trip, and as soon as it finishes a trip it starts the next one, so it makes a new trip every times[i] minutes. The buses run independently of each other.
The city wants totalTrips trips completed in total across all buses. Return the smallest number of minutes after which the buses together have completed at least totalTrips trips. The answer can be very large, so use a 64-bit integer, and do not simulate minute by minute.
Example 1
- Input:
- times = [4,7], totalTrips = 6
- Output:
- 16
- Explanation:
After 14 minutes bus 1 completed 3 trips and bus 2 completed 2, which is 5. After 16 minutes it is 4 + 2 = 6, so 16 minutes are needed.
Example 2
- Input:
- times = [5], totalTrips = 3
- Output:
- 15
- Explanation:
A single bus finishes its third trip at minute 15.
Constraints
1 ≤ times.length ≤ 105
1 ≤ times[i], totalTrips ≤ 107
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n log(T * min(times)))
- Space
- O(1)