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 <iostream>
2#include <vector>
3#include <cmath>
4
5int minSpeedOnTime(std::vector<int>& dist, double hour) {
6 int left = 1, right = 1e7;
7 while (left < right) {
8 int mid = (left + right) / 2;
9 double time = 0.0;
10 for (int i = 0; i < dist.size(); ++i) {
11 if (i < dist.size() - 1) {
12 time += std::ceil((double)dist[i] / mid);
13 } else {
14 time += (double)dist[i] / mid;
}
}
if (time <= hour) {
right = mid;
} else {
left = mid + 1;
}
}
return left == 1e7 ? -1 : left;
}
int main() {
std::vector<int> dist = {1, 3, 2};
double hour = 6;
std::cout << minSpeedOnTime(dist, hour) << std::endl;
return 0;
}Using binary search, we iterate over possible speeds to simulate the commute. The code checks if the chosen mid speed allows you to reach within the available hours by rounding up time for each train, except the last. The final speed when search range converges is the minimum required.