Sponsored
Sponsored
Idea: To find the minimum positive integer speed that allows you to reach the office in the given time, you can use binary search on the speed. Initialize the left boundary to 1 (minimum speed) and right boundary to a large number (e.g., 10^7, as specified in the problem statement), then narrow down the possible speed by simulating the commute.
Steps:
If you narrow down to a result, it is the minimum speed required. If search is exhausted without finding a valid speed, return -1.
Time Complexity: O(n log k), where n is the number of train distances and k is the maximum speed (10^7).
Space Complexity: O(1), as the solution does not require any extra space beyond a fixed set of variables.
1import math
2
3def minSpeedOnTime(dist, hour):
4 left, right = 1, 10000000
5 while left < right:
6
The solution utilizes binary search to efficiently determine the minimum speed necessary to reach the destination within the hour limit. Python's float arithmetic and math.ceil function ascertain the feasibility of each candidate speed until convergence.