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.
1using System;
2public class Solution {
3 public int MinSpeedOnTime(int[] dist, double hour) {
4 int left = 1, right = 10000000;
5 while (left < right) {
6 int mid = (left + right) / 2;
7 double time = 0.0;
8 for (int i = 0; i < dist.Length; ++i) {
9 if (i < dist.Length - 1) {
10 time += Math.Ceiling((double)dist[i] / mid);
11 } else {
12 time += (double)dist[i] / mid;
13 }
}
if (time <= hour) {
right = mid;
} else {
left = mid + 1;
}
}
return left == 10000000 ? -1 : left;
}
public static void Main() {
int[] dist = {1, 3, 2};
double hour = 6;
Console.WriteLine(new Solution().MinSpeedOnTime(dist, hour));
}
}The C# solution employs binary search to find the minimum speed that trains can travel while fulfilling the given hour constraint. Integer and double arithmetic enable accurate calculations for time consideration and speed adjustment.