2187.Minimum Time to Complete Trips
===

###### tags: `Medium`,`Array`,`Binary Search`

[2187. Minimum Time to Complete Trips](https://leetcode.com/problems/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**.

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` <= 10^5^
* 1 <= `time[i]`, `totalTrips` <= 10^7^

### 解答
#### Python

class Solution:
    def minimumTime(self, time: List[int], totalTrips: int) -> int:
        l, r = 0, min(time) * totalTrips
        while l < r:
            m = (l + r) // 2
            trips = sum([m // t for t in time])
            if trips >= totalTrips:
                r = m
            else:
                l = m + 1
        return l

> [name=Yen-Chi Chen][time=Tue, Mar 7, 2023]

#### Javascript

function minimumTime(time, totalTrips) {
  let min = 1;
  let max = Infinity;
  for (const t of time) {
    max = Math.min(max, t * totalTrips);
  }

  while (max > min) {
    const mid = Math.floor((min + max) / 2);
    let trip = 0;
    for (const t of time) {
      trip += Math.floor(mid / t);
    }

    if (trip >= totalTrips) {
      max = mid;
    } else {
      min = mid + 1;
    }
  }

  return min;
}

> 跟吉神學習了，本來我max還不知道要設多少。
> [name=Marsgoat][time=Mar 8, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)