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
    }
}

1870 - Minimum Speed to Arrive on Time

1870. Minimum Speed to Arrive on Time

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

1870. Minimum Speed to Arrive on Time

Level

Description

Solution

All Problems

All Solutions