1870. Minimum Speed to Arrive on Time
Problem Description
You have a specific amount of time, hour
, to commute to the office using a series of trains. Each segment of your journey has a fixed distance, and all segments must be completed sequentially. The key challenge is that trains can only leave at the start of each hour, meaning you might need to wait before boarding the next train. For instance, if a train ride takes 1.5 hours, a 0.5-hour wait is required before the next train departs. Your task is to determine the minimum train speed (in km/h) required to reach the office on time. This speed must be a positive integer, and if it's impossible to arrive on time, the function should return -1
. The provided constraints ensure that the solution won't be higher than 10^7
and the hour
won't have more than two decimals.
Intuition
The minimum speed to reach on time is not evidently clear and can range from 1 to 10^7
. To find the minimum speed efficiently, we employ a binary search strategy. A binary search halves the potential search space by checking whether a particular condition (in this case, being able to make it to the office on time at a certain speed) is met or not.
Here's the thought process for arriving at the binary search solution:
-
If a particular speed allows us to reach the office on time (
hour
or less), then any speed higher than this would also suffice. Conversely, any speed lower than a speed that does not make it on time is also inadequate. -
We define a
check
function to determine if the current speed is sufficient to reach on time, considering the waiting time between train rides. The last ride doesn't require any wait time. -
Using a binary search, we find the minimum speed at which the
check
function returnstrue
. As speeds lower than this minimum won't help us arrive on time, we restrict our search to the range where we might meet the condition. -
We initiate a search range from 1 to
10^7
and repeatedly narrow it down using thecheck
function until we pinpoint the minimum required speed. -
If we're unable to find a speed that allows for a timely arrival within the maximum speed limit, we return
-1
, indicating that it's not possible to be punctual.
The binary search is implemented using the bisect_left
function from the Python library. It operates by taking the range as an iterable, the condition to check, and a key function, which in this case is the check
function. It then finds the leftmost value in the sorted range that satisfies the condition.
Learn more about Binary Search patterns.
Solution Approach
The solution to the problem leverages the binary search algorithm, which is ideal for the scenario because of its ability to reduce the search space in half with each iteration. The objective of the binary search in this context is to discover the minimum integer speed so that the total travel time does not exceed the given hour
.
Here's how the binary search is used to implement the solution:
-
Define a
check
function: This function accepts a speed and calculates the total time taken to travel all distances in thedist
array at that speed. For all train segments except the last, the time is rounded up to the nearest integer to account for the rule that trains leave only at the beginning of every hour. For the last train segment, exact time can be used since you don't need to wait for another train after. -
Binary search algorithm: We perform a binary search to find the appropriate speed using two boundaries denoted as
left
andright
, initially set to1
and10^7 + 1
respectively. The algorithm iteratively narrows these boundaries until the optimal speed is found.-
Initialization: We set our initial search interval from
1
to10^7 + 1
, to cover the entire range of possible speeds as per the problem's constraints. -
Binary search loop: At each step of the loop, the midpoint of the current interval is computed and passed to the
check
function. Based on the function's output:-
If the check is
true
, it means the current speed or any higher could be the solution; hence we narrow the search to the lower half of the interval (right = mid
). -
If the check is
false
, it means the current speed is too slow, so we narrow the search to the upper half of the interval (left = mid + 1
).
-
-
Checking for impossibility: If it's determined that even the highest possible speed doesn't allow us to be on time (at after searching the entire interval), we conclude that it's impossible to reach on time and return
-1
.
-
-
Using
bisect_left
: The binary search is succinctly executed using thebisect_left
function from thebisect
module, which is applied to a range object representing our potential speeds. We use a lambda function as the key to thebisect_left
, which internally applies thecheck
function to the speeds to handle the binary search. The result is then adjusted by adding1
to the speed sincebisect_left
finds the leftmost place whereTrue
could be inserted without changing the order. -
Mathematical and logical operations: The algorithm uses integer division (
math.ceil
) to account for the waiting time at stations and leverages boolean conditions to implement the binary search logic.
To sum it up, the solution efficiently navigates through a potentially massive search space to find the minimum speed necessary for timely arrival, using binary search principles encapsulated in Python's bisect_left
function.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Suppose we have the following input parameters:
- Distances array
dist = [5, 7, 3]
, representing the distances of each train segment of the journey. - Total time allowed
hour = 2.5
hours to reach the office.
Now, let's walk through the binary search approach to find the minimum train speed required for the given journey:
-
Initialization: We start with a potential speed range of
1
to10^7 + 1
. This means ourleft
boundary is1
and ourright
boundary is10^7 + 1
. -
First iteration of binary search:
- The mid-speed is
(1 + 10000001) / 2 = 5000001
. - We check if a train at 5000001 km/h can reach within
2.5
hours. - We calculate the time for each segment at
5000001
km/h:- Segment 1:
5 / 5000001
hours - No need to round up because there is another segment after. - Segment 2:
7 / 5000001
hours - No need to round up because there is another segment after. - Segment 3:
3 / 5000001
hours - This is the last segment, we take the exact time.
- Segment 1:
- We sum up these times and find that the total time taken is way less than
2.5
hours, so we setright
to5000001
.
- The mid-speed is
-
Second iteration of binary search:
- The new mid-speed is
(1 + 5000001) / 2 = 2500001
. - We perform the same
check
function for the new mid-speed. - Again, the speed is high enough to get us there in under
2.5
hours, so we adjustright
to2500001
.
- The new mid-speed is
-
Continuing the binary search:
- We continue halving the interval and checking, bringing the
left
andright
boundaries closer after each iteration.
- We continue halving the interval and checking, bringing the
-
Final step:
-
Eventually, we narrow down to a range where moving
left
by one would causecheck
to yieldfalse
, and we settle on theright
boundary as the minimum sufficient speed. -
Suppose after multiple iterations, we find that at
10
km/h,check
isfalse
, but at11
km/h,check
istrue
. This tells us that11
km/h is the minimum speed required to reach the office on time.
-
-
Result:
- The binary search terminates when
left
is equal toright
, which means we've found the minimum train speed satisfying the conditions. - If no such speed allows arrival within
2.5
hours, our search boundaries would converge such thatcheck
always returnsfalse
, and we return-1
.
- The binary search terminates when
In our example, by following the binary search algorithm steps, we would eventually find that the minimum speed required for the distances [5, 7, 3]
to be covered within 2.5
hours is 11
km/h. This result is achieved without testing every speed from 1
to 10^7
individually.
Solution Implementation
1from bisect import bisect_left
2import math
3from typing import List
4
5class Solution:
6 def minSpeedOnTime(self, dist: List[int], hour: float) -> int:
7 # Helper function to check if a given speed is sufficient to arrive on time
8 def is_speed_sufficient(speed):
9 total_time = 0
10 for i, distance in enumerate(dist):
11 # For the last distance, we don't need to ceil as we can arrive exactly on time
12 if i == len(dist) - 1:
13 total_time += distance / speed
14 else: # For all others, we'll ceil to account for the fact that we can't travel partial units of distance in less than an hour
15 total_time += math.ceil(distance / speed)
16 return total_time <= hour
17
18 # Set the maximum possible speed based on constraints; here, arbitrarily set to 10^7
19 max_possible_speed = 10**7 + 1
20
21 # Binary search to find the minimum sufficient speed [1, max_possible_speed)
22 # We are adding 1 because `bisect_left` will return the position to insert True to maintain sorted order
23 # So we need to convert this position to the corresponding speed by adding 1
24 minimum_sufficient_speed = bisect_left(range(1, max_possible_speed), True, key=is_speed_sufficient) + 1
25
26 # If the speed is equal to the maximum possible speed, it means it wasn't possible to arrive on time
27 # So we return -1; otherwise, return the minimum sufficient speed
28 return -1 if minimum_sufficient_speed == max_possible_speed else minimum_sufficient_speed
29
1class Solution {
2
3 public int minSpeedOnTime(int[] distances, double hour) {
4 int lowerBound = 1; // Defines the minimum possible speed
5 int upperBound = (int) 1e7; // Defines the maximum possible speed, assuming a constraints' defined upper limit
6
7 // Binary search to find minimum speed necessary to arrive on time
8 while (lowerBound < upperBound) {
9 int midSpeed = (lowerBound + upperBound) / 2; // Use mid as the candidate speed
10 if (canArriveOnTime(distances, midSpeed, hour)) {
11 upperBound = midSpeed; // If we can arrive on time with this speed, try lower speed
12 } else {
13 lowerBound = midSpeed + 1; // Otherwise, try a higher speed
14 }
15 }
16
17 // Check if the minimum speed found allows arrival on time
18 return canArriveOnTime(distances, lowerBound, hour) ? lowerBound : -1;
19 }
20
21 // Helper function to check if we can arrive on time given the distances, speed and hour
22 private boolean canArriveOnTime(int[] distances, int speed, double hour) {
23 // Total time taken to travel all distances at the given speed
24 double totalTime = 0.0;
25 for (int i = 0; i < distances.length; ++i) {
26 double segmentTime = (double)distances[i] / speed;
27 // Ceil the time for all segments except the last (no need to wait for a whole hour on the last segment)
28 totalTime += (i == distances.length - 1) ? segmentTime : Math.ceil(segmentTime);
29 }
30 return totalTime <= hour; // Return true if time does not exceed the given hour
31 }
32}
33
1class Solution {
2public:
3 // Function to find the minimum speed needed to arrive on time
4 int minSpeedOnTime(vector<int>& distances, double hour) {
5 // Initialize binary search bounds
6 int minSpeed = 1, maxSpeed = 1e7;
7
8 // Perform binary search to find the minimum feasible speed
9 while (minSpeed < maxSpeed) {
10 int midSpeed = (minSpeed + maxSpeed) >> 1; // Calculate mid speed
11
12 // Check if current speed meets the required time
13 if (canArriveOnTime(distances, midSpeed, hour)) {
14 maxSpeed = midSpeed; // If yes, search in the lower half
15 } else {
16 minSpeed = midSpeed + 1; // If no, search in the upper half
17 }
18 }
19
20 // After binary search, check if the left bound allows to arrive on time
21 return canArriveOnTime(distances, minSpeed, hour) ? minSpeed : -1;
22 }
23
24 // Helper function to check if it is possible to arrive on time at the given speed
25 bool canArriveOnTime(vector<int>& distances, int speed, double hour) {
26 double totalTime = 0; // Variable to store total time taken
27
28 for (int i = 0; i < distances.size(); ++i) {
29 double travelTime = static_cast<double>(distances[i]) / speed;
30
31 // For all but the last distance, we round up the travel time to the nearest whole number
32 // since you can't travel a fraction of a distance without spending the whole hour
33 totalTime += (i == distances.size() - 1) ? travelTime : ceil(travelTime);
34 }
35
36 // Return true if the total time does not exceed the given hour, false otherwise
37 return totalTime <= hour;
38 }
39};
40
1/**
2 * Calculate the minimum travel speed required to complete a given set of distances within a specified time.
3 *
4 * @param {number[]} distances - An array of distances to travel.
5 * @param {number} timeLimit - The time limit to complete all travels.
6 * @return {number} - The minimum speed required to be on time, or -1 if it's impossible.
7 */
8function minSpeedOnTime(distances: number[], timeLimit: number): number {
9 // Check if the travel is possible within the time limit. If there are more distances
10 // than the ceiling value of hours, it's impossible to complete on time.
11 if (distances.length > Math.ceil(timeLimit)) return -1;
12
13 let minSpeed = 1; // Lower bound for binary search (minimum possible speed).
14 let maxSpeed = 10 ** 7; // Upper bound for binary search (arbitrarily high speed).
15
16 while (minSpeed < maxSpeed) {
17 let midSpeed = Math.floor((minSpeed + maxSpeed) / 2);
18 if (arriveOnTime(distances, midSpeed, timeLimit)) {
19 maxSpeed = midSpeed;
20 } else {
21 minSpeed = midSpeed + 1;
22 }
23 }
24
25 // The left boundary of the binary search represents the minimum speed at which we can arrive on time.
26 return minSpeed;
27}
28
29/**
30 * Helper function to check if it's possible to arrive on time at the given speed.
31 *
32 * @param {number[]} distances - An array of distances to travel.
33 * @param {number} speed - The traveling speed.
34 * @param {number} timeLimit - The time limit to complete all travels.
35 * @return {boolean} - Returns true if it's possible to arrive on time, otherwise false.
36 */
37function arriveOnTime(distances: number[], speed: number, timeLimit: number): boolean {
38 let totalTime = 0.0;
39 let n = distances.length;
40
41 for (let i = 0; i < n; i++) {
42 let travelTime = distances[i] / speed;
43 // For all but the last distance, round the travel time up to the nearest whole number,
44 // since you can't travel a fraction of the distance at a consistent speed.
45 if (i != n - 1) {
46 travelTime = Math.ceil(travelTime);
47 }
48 totalTime += travelTime;
49 }
50 // Compare the total time taken to travel at the given speed with the time limit.
51 return totalTime <= timeLimit;
52}
53
Time and Space Complexity
The time complexity of the minSpeedOnTime
function is determined by the binary search and the check function that is called at each step of the binary search.
The binary search runs in O(log R)
, where R
is the range of possible speeds, which in this case is 10^7
. The +1
correction does not affect the logarithmic complexity.
The check
function runs in O(N)
, where N
is the number of elements in the dist
list because it needs to iterate over all the distances. Inside the check function, math.ceil
function is called which has a constant time O(1)
. Therefore, for each call of the check
function, the time complexity is linear with respect to the number of distances.
Therefore, the overall time complexity of the function is O(N log R)
where N
is the number of distances in the dist
list and R
is 10^7
.
The space complexity of the function is O(1)
. No additional space is allocated that grows with the size of the input, except for the variable res
, which uses a constant amount of space.
Learn more about how to find time and space complexity quickly using problem constraints.
How many ways can you arrange the three letters A, B and C?
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first