Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1870.html

1870. Minimum Speed to Arrive on Time

Level

Medium

Description

You are given a floating-point number hour, representing the amount of time you have to reach the office. To commute to the office, you must take n trains in sequential order. You are also given an integer array dist of length n, where dist[i] describes the distance (in kilometers) of the i-th train ride.

Each train can only depart at an integer hour, so you may need to wait in between each train ride.

  • For example, if the 1st train ride takes 1.5 hours, you must wait for an additional 0.5 hours before you can depart on the 2nd train ride at the 2 hour mark.

Return the minimum positive integer speed (in kilometers per hour) that all the trains must travel at for you to reach the office on time, or -1 if it is impossible to be on time.

Tests are generated such that the answer will not exceed 10^7 and hour will have at most two digits after the decimal point.

Example 1:

Input: dist = [1,3,2], hour = 6

Output: 1

Explanation: At speed 1:

  • The first train ride takes 1/1 = 1 hour.
  • Since we are already at an integer hour, we depart immediately at the 1 hour mark. The second train takes 3/1 = 3 hours.
  • Since we are already at an integer hour, we depart immediately at the 4 hour mark. The third train takes 2/1 = 2 hours.
  • You will arrive at exactly the 6 hour mark.

Example 2:

Input: dist = [1,3,2], hour = 2.7

Output: 3

Explanation: At speed 3:

  • The first train ride takes 1/3 = 0.33333 hours.
  • Since we are not at an integer hour, we wait until the 1 hour mark to depart. The second train ride takes 3/3 = 1 hour.
  • Since we are already at an integer hour, we depart immediately at the 2 hour mark. The third train takes 2/3 = 0.66667 hours.
  • You will arrive at the 2.66667 hour mark.

Example 3:

Input: dist = [1,3,2], hour = 1.9

Output: -1

Explanation: It is impossible because the earliest the third train can depart is at the 2 hour mark.

Constraints:

  • n == dist.length
  • 1 <= n <= 10^5
  • 1 <= dist[i] <= 10^5
  • 1 <= hour <= 10^9
  • There will be at most two digits after the decimal point in hour.

Solution

The maximum possible speed is 10^7. If it is still impossible to arrive on time using the maximum possible speed, return -1. Then let high = 10000000 and low = 1, and use binary search to find the minimum speed to arrive on time.

  • class Solution {
        public int minSpeedOnTime(int[] dist, double hour) {
            int high = 10000000;
            if (!canArrive(dist, hour, high))
                return -1;
            int low = 1;
            while (low < high) {
                int mid = (high - low) / 2 + low;
                if (canArrive(dist, hour, mid))
                    high = mid;
                else
                    low = mid + 1;
            }
            return low;
        }
    
        public boolean canArrive(int[] dist, double hour, int speed) {
            double total = 0;
            int length = dist.length;
            for (int i = 0; i < length; i++) {
                if (i == length - 1)
                    total += 1.0 * dist[i] / speed;
                else {
                    int curr = dist[i] / speed;
                    if (dist[i] % speed != 0)
                        curr++;
                    total += curr;
                }
            }
            return total <= hour;
        }
    }
    
    ############
    
    class Solution {
        public int minSpeedOnTime(int[] dist, double hour) {
            int left = 1, right = (int) 1e7;
            while (left < right) {
                int mid = (left + right) >> 1;
                if (check(dist, mid, hour)) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            return check(dist, left, hour) ? left : -1;
        }
    
        private boolean check(int[] dist, int speed, double hour) {
            double res = 0;
            for (int i = 0; i < dist.length; ++i) {
                double cost = dist[i] * 1.0 / speed;
                res += (i == dist.length - 1 ? cost : Math.ceil(cost));
            }
            return res <= hour;
        }
    }
    
  • // OJ: https://leetcode.com/problems/minimum-speed-to-arrive-on-time/
    // Time: O(NlogT) where T is the maximum possible speed
    // Space: O(1)
    class Solution {
        bool valid(vector<int>& A, int speed, double hour) {
            double time = 0;
            for (int i = 0; i < A.size(); ++i) {
                time = ceil(time);
                time +=  (double)A[i] / speed;
                if (time > hour) return false;
            }
            return true;
        }
    public:
        int minSpeedOnTime(vector<int>& A, double hour) {
            if (hour < A.size() - 1) return -1;
            long L = 1, R = 1e7;
            while (L <= R) {
                long M = (L + R) / 2;
                if (valid(A, M, hour)) R = M - 1;
                else L = M + 1;
            }
            return L > 1e7 ? -1 : L;
        }
    };
    
  • class Solution:
        def minSpeedOnTime(self, dist: List[int], hour: float) -> int:
            def check(speed):
                res = 0
                for i, d in enumerate(dist):
                    res += (d / speed) if i == len(dist) - 1 else math.ceil(d / speed)
                return res <= hour
    
            r = 10**7 + 1
            ans = bisect_left(range(1, r), True, key=check) + 1
            return -1 if ans == r else ans
    
    ############
    
    # 1870. Minimum Speed to Arrive on Time
    # https://leetcode.com/problems/minimum-speed-to-arrive-on-time/
    
    class Solution:
        def minSpeedOnTime(self, dist: List[int], hour: float) -> int:
            n = len(dist)
    
            def good(x):
                t = 0
                
                for i, d in enumerate(dist):
                    if i != n - 1:
                        h = math.ceil(d / x)
                    else:
                        h = d / x
    
                    t += h
    
                return t <= hour
                
    
            left, right = 1, 10 ** 7 + 1
            
            while left < right:
                mid = left + (right - left) // 2
                
                if good(mid):
                    right = mid
                else:
                    left = mid + 1
            
            return left if left <= 10 ** 7 else -1
                
            
    
    
  • func minSpeedOnTime(dist []int, hour float64) int {
    	n := len(dist)
    	const mx int = 1e7
    	x := sort.Search(mx, func(s int) bool {
    		s++
    		var cost float64
    		for _, v := range dist[:n-1] {
    			cost += math.Ceil(float64(v) / float64(s))
    		}
    		cost += float64(dist[n-1]) / float64(s)
    		return cost <= hour
    	})
    	if x == mx {
    		return -1
    	}
    	return x + 1
    }
    
  • /**
     * @param {number[]} dist
     * @param {number} hour
     * @return {number}
     */
    var minSpeedOnTime = function (dist, hour) {
        if (dist.length > Math.ceil(hour)) return -1;
        let left = 1,
            right = 10 ** 7;
        while (left < right) {
            let mid = (left + right) >> 1;
            if (arriveOnTime(dist, mid, hour)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    };
    
    function arriveOnTime(dist, speed, hour) {
        let res = 0.0;
        let n = dist.length;
        for (let i = 0; i < n; i++) {
            let cost = parseFloat(dist[i]) / speed;
            if (i != n - 1) {
                cost = Math.ceil(cost);
            }
            res += cost;
        }
        return res <= hour;
    }
    
    
  • impl Solution {
        pub fn min_speed_on_time(dist: Vec<i32>, hour: f64) -> i32 {
            let n = dist.len();
    
            let check = |speed| {
                let mut cur = 0.;
                for (i, &d) in dist.iter().enumerate() {
                    if i == n - 1 {
                        cur += d as f64 / speed as f64;
                    } else {
                        cur += (d as f64 / speed as f64).ceil();
                    }
                }
                cur <= hour
            };
    
            let mut left = 1;
            let mut right = 1e7 as i32;
            while left < right {
                let mid = left + (right - left) / 2;
                if !check(mid) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
    
            if check(left) {
                return left;
            }
            -1
        }
    }
    
    

All Problems

All Solutions