
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.
1public class MinSpeed {
2 public static int minSpeedOnTime(int[] dist, double hour) {
3 int left = 1, right =
This Java solution accomplishes the same task with the binary search. Iteratively check midpoint as a candidate speed and compute total travel time, adjusting search boundaries depending on whether the time constraint is met.