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.
1#include <stdio.h>
2#include <math.h>
3
4int minSpeedOnTime(int* dist, int distSize, double hour) {
5
The solution involves performing a binary search over possible speeds. The minSpeedOnTime function iterates over each train's distance at a given mid speed, calculating the time taken accounting for waiting until the next hour if necessary. The result is a narrowed-down speed that allows for reaching within the specified hour, making use of ceiling round-ups for all train rides except for the last one.