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 ith 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
1sttrain ride takes1.5hours, you must wait for an additional0.5hours before you can depart on the2ndtrain 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 107 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.length1 <= n <= 1051 <= dist[i] <= 1051 <= hour <= 109- There will be at most two digits after the decimal point in
hour.
Binary search.
Template 1:
boolean check(int x) {}
int search(int left, int right) {
while (left < right) {
int mid = (left + right) >> 1;
if (check(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}Template 2:
boolean check(int x) {}
int search(int left, int right) {
while (left < right) {
int mid = (left + right + 1) >> 1;
if (check(mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}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 ansclass 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;
}
}class Solution {
public:
int minSpeedOnTime(vector<int>& dist, double hour) {
int left = 1, right = 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;
}
bool check(vector<int>& dist, int speed, double hour) {
double res = 0;
for (int i = 0; i < dist.size(); ++i) {
double cost = dist[i] * 1.0 / speed;
res += (i == dist.size() - 1 ? cost : ceil(cost));
}
return res <= hour;
}
};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
}
}