##### Welcome to Subscribe On Youtube

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

# 1870. Minimum Speed to Arrive on Time

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

############

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