#1870

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Minimum Speed to Arrive on Time

This problem asks to find the minimum speed of trains to reach on time using binary search.

Problem Statement

You have a total of n trains to take, each with a distance described by an array dist. You must reach the office within a given time hour. You are tasked with determining the minimum speed in kilometers per hour at which all the trains must travel to reach on time. If it is impossible to reach on time, return -1.

Each train ride has a distance and can only depart at integer hours. If you do not reach the next departure time at an integer hour, you must wait until the next whole hour before departing. Your goal is to find the minimum speed such that you arrive at your destination within the given time.

Examples

Example 1

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

Output: 1

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

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

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.

Solution Approach

Binary Search on Speed

To solve this, we perform binary search on the possible speeds, ranging from 1 to the maximum possible speed. The key is to calculate the total time it takes for all trains to reach the destination at each potential speed, and compare it with the given hour to determine feasibility.

Calculate Time for Each Speed

For each speed, calculate the total travel time by dividing each distance by the current speed and adjusting for the necessary waiting time between trains. The approach is to sum these times and check if the total time is within the allowed hour.

Edge Case Handling

Consider edge cases such as when it's impossible to reach on time, like when the given hour is too small to accommodate the journey, or when no valid speed can allow arrival within the specified time.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the binary search solution is O(n log(maxSpeed)), where n is the number of trains and maxSpeed is the upper bound on possible speeds. The space complexity is O(1) because the solution uses only a constant amount of space aside from the input.

What Interviewers Usually Probe

The candidate should show comfort with binary search, applying it to a non-trivial range (speed).
The candidate should be able to clearly explain how to handle integer hour restrictions and waiting times.
Expect clarity in distinguishing between calculating travel time and handling edge cases where the trip cannot be completed on time.

Common Pitfalls or Variants

Common pitfalls

Overlooking the waiting time between train rides when calculating travel times.
Not correctly adjusting for the fact that you can only depart at integer hours.
Incorrect binary search bounds or failure to optimize the range for speed effectively.

Follow-up variants

Increase the difficulty by adding more complex conditions, like varying speeds or multiple constraints on time.
Modify the problem to consider alternative transportation methods or constraints that could affect the time.
Extend the problem to consider dynamic changes in speed or delays during travel.

FAQ

What is the main pattern for solving the Minimum Speed to Arrive on Time problem?

The main pattern is binary search over the valid answer space, where we test different speeds to see if they allow us to arrive on time.

How does binary search apply to the Minimum Speed to Arrive on Time problem?

Binary search helps narrow down the minimum possible speed that will allow you to reach the destination on time by efficiently checking the total travel time at each speed.

What are the edge cases to consider in the Minimum Speed to Arrive on Time problem?

Edge cases include when it's impossible to reach on time due to insufficient time or when no valid speed can allow arrival within the given hour.

Can the Minimum Speed to Arrive on Time problem be solved without binary search?

While a brute force approach can work, binary search is necessary to optimize the solution and handle larger inputs efficiently.

What is the time complexity of solving the Minimum Speed to Arrive on Time problem?

The time complexity is O(n log(maxSpeed)), where n is the number of trains, and maxSpeed is the maximum possible speed.

terminal

Solution

Solution 1: Binary Search

We notice that if a speed value $v$ allows us to arrive within the stipulated time, then for any $v' > v$, we can also definitely arrive within the stipulated time. This exhibits monotonicity, hence we can use binary search to find the smallest speed value that meets the condition.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:
        def check(v: int) -> bool:
            s = 0
            for i, d in enumerate(dist):
                t = d / v
                s += t if i == len(dist) - 1 else ceil(t)
            return s <= hour

        if len(dist) > ceil(hour):
            return -1
        r = 10**7 + 1
        ans = bisect_left(range(1, r), True, key=check) + 1
        return -1 if ans == r else ans

Continue Practicing

#1862 sum of floored pairs #1855 maximum distance between a pair of values #1851 minimum interval to include each query