# Minimum Speed to Arrive on Time
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-speed-to-arrive-on-time)
Canonical: https://scaleengineer.com/dsa/problems/minimum-speed-to-arrive-on-time
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
---
## Problem
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 `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 `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.length`
* `1 <= n <= 105`
* `1 <= dist[i] <= 105`
* `1 <= hour <= 109`
* There will be at most two digits after the decimal point in `hour`.

# Approaches
## Brute Force with Linear Search
This approach involves a linear scan through all possible speeds. Starting from a speed of 1, we check each integer speed one by one. For every speed, we calculate the total time it would take to travel all the distances, considering the waiting time between trains. The first speed that results in a total time less than or equal to the allowed `hour` is the minimum speed we are looking for. If we exhaust all possible speeds up to a given limit without finding a solution, we conclude it's impossible.
**Time:** O(K * N), where `N` is the number of trains (`dist.length`) and `K` is the maximum speed to check (up to 10^7). This is too slow for the given constraints. · **Space:** O(1), as we only use a few variables to store the current state.
**Pros:** Simple to understand and implement.; Correctly finds the minimum speed if one exists within the searched range.
**Cons:** Extremely inefficient due to the large search space for speed.; Will result in a 'Time Limit Exceeded' (TLE) error for larger constraints.
### Explanation
The core of this method is a helper function, `calculateTime(dist, speed)`, which computes the total travel time for a given speed. This function iterates through the `dist` array. For the first `n-1` trains, the time taken is `dist[i] / speed`, and since we must wait for the next integer hour, we take the ceiling of this value. For the last train, we simply add `dist[n-1] / speed` as no further waiting is required.

The main function then calls this helper in a loop, starting `speed` from 1. If `calculateTime` returns a total time less than or equal to `hour`, we've found our answer. The problem statement guarantees that the answer will not exceed 10^7, so we can use this as our search limit. If the loop completes without finding a suitable speed, we return -1.

```java
class Solution {
    public int minSpeedOnTime(int[] dist, double hour) {
        // The problem states the answer will not exceed 10^7.
        int maxSpeed = 10000000;
        for (int speed = 1; speed <= maxSpeed; speed++) {
            if (calculateTime(dist, speed) <= hour) {
                return speed;
            }
        }
        return -1;
    }

    private double calculateTime(int[] dist, int speed) {
        double totalTime = 0.0;
        for (int i = 0; i < dist.length - 1; i++) {
            totalTime += Math.ceil((double) dist[i] / speed);
        }
        totalTime += (double) dist[dist.length - 1] / speed;
        return totalTime;
    }
}
```
### Algorithm
- Iterate through all possible integer speeds `s` starting from 1 up to a reasonable upper bound (e.g., `10^7`, as suggested by the problem constraints).
- For each speed `s`, create a helper function to calculate the total time required to complete all journeys.
- Inside the helper function:
  - Initialize `totalTime = 0.0`.
  - For the first `n-1` train rides, calculate the time as `dist[i] / s`. Since you must wait until the next integer hour, add `ceil(dist[i] / s)` to `totalTime`.
  - For the last train ride, no waiting is needed, so simply add `dist[n-1] / s` to `totalTime`.
- If the calculated `totalTime` is less than or equal to the given `hour`, then `s` is the minimum possible speed. Return `s` immediately.
- If the loop completes without finding any valid speed, it means it's impossible to arrive on time. Return -1.

## Binary Search on the Answer
A more efficient approach is to use binary search on the answer (the speed). The key observation is that if a certain speed `s` allows you to arrive on time, any speed greater than `s` will also work. This monotonic property (as speed increases, time decreases) makes the problem suitable for binary search. We can search for the minimum valid speed in a range from 1 to a reasonable maximum (like 10^7). For each candidate speed, we check if it's possible to arrive on time. Based on the result, we eliminate half of the search space, drastically reducing the number of checks needed compared to the brute-force method.
**Time:** O(N * log(K)), where `N` is the number of trains and `K` is the size of the speed search range (10^7). The `log(K)` factor comes from binary search, and for each step, we do an O(N) calculation. This is very efficient. · **Space:** O(1), as the binary search is performed in-place and the helper function uses constant extra space.
**Pros:** Highly efficient, with a logarithmic time complexity with respect to the search range.; Guaranteed to find the optimal solution and pass within the time limits.
**Cons:** Slightly more complex to conceptualize than a linear search.; Relies on correctly identifying the monotonic property of the problem.
### Explanation
We define a search space for the speed, from a lower bound of 1 to an upper bound of 10^7. We then perform a binary search on this range.

For each `mid` speed in our search:
1.  We calculate the total time required using this `mid` speed. The calculation is the same as in the brute-force approach: sum the ceiling of travel times for the first `n-1` trains and add the exact travel time for the last train.
2.  If the calculated time is less than or equal to `hour`, it means this `mid` speed is a potential answer. Since we are looking for the *minimum* speed, we try to find an even smaller valid speed by narrowing our search to the lower half (`high = mid - 1`). We store `mid` as our current best answer.
3.  If the calculated time is greater than `hour`, the `mid` speed is too slow. We must increase the speed, so we narrow our search to the upper half (`low = mid + 1`).

The search continues until the `low` and `high` pointers cross. The last valid speed we recorded is the minimum integer speed required. If no speed within the search range is valid, we return -1.

An initial check can be performed as an optimization: the total time will always be greater than `n-1` for any finite speed (since each of the first `n-1` trips takes at least 1 hour after waiting). If the given `hour` is less than or equal to `n-1`, it's impossible to arrive on time, so we can immediately return -1.

```java
class Solution {
    public int minSpeedOnTime(int[] dist, double hour) {
        int n = dist.length;
        // Optimization: If hour is too small, it's impossible.
        // Each of the first n-1 trips takes at least 1 hour.
        if (hour <= (double) n - 1 && n > 1) {
            return -1;
        }

        int low = 1;
        int high = 10000000; // Given constraint on the answer
        int minSpeed = -1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            // mid will not be 0 since low starts at 1.

            if (canArriveOnTime(dist, mid, hour)) {
                minSpeed = mid;
                high = mid - 1; // Try for a smaller speed
            } else {
                low = mid + 1; // Speed is too slow, need to increase
            }
        }
        return minSpeed;
    }

    private boolean canArriveOnTime(int[] dist, int speed, double hour) {
        double totalTime = 0.0;
        for (int i = 0; i < dist.length - 1; i++) {
            totalTime += Math.ceil((double) dist[i] / speed);
        }
        totalTime += (double) dist[dist.length - 1] / speed;
        return totalTime <= hour;
    }
}
```
### Algorithm
- Recognize that the total travel time is a non-increasing function of speed. This monotonicity allows for binary search.
- Define a search range for the speed. The lower bound `low` is 1, and the upper bound `high` can be set to `10^7` (as per the problem's hint) or a slightly larger safe number.
- Initialize the answer `minSpeed = -1`.
- While `low <= high`:
  - Calculate the middle speed `mid = low + (high - low) / 2`.
  - Use a helper function to calculate the total time required for speed `mid`.
  - If the calculated time is less than or equal to `hour`:
    - `mid` is a potential answer. Store it: `minSpeed = mid`.
    - Try to find an even smaller speed by searching in the lower half: `high = mid - 1`.
  - Otherwise (if the time is greater than `hour`):
    - `mid` is too slow. Search for a faster speed in the upper half: `low = mid + 1`.
- After the loop, `minSpeed` will hold the minimum valid speed found, or -1 if none was found.

# Solutions
### Java

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

### JavaScript

```javascript
/** * @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;
}

```

### CPP

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

```

### Python

```python
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

```