2187.Minimum Time to Complete Trips

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

題目描述

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⁵
1 <= time[i], totalTrips <= 10⁷

解答

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

Yen-Chi ChenTue, 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還不知道要設多少。
MarsgoatMar 8, 2023

Reference

回到題目列表