Leetcode 1870: Minimum Speed to Arrive on Time
You are given a list of n train ride distances and a floating-point number hour which indicates the total time you have to reach your destination. You need to determine the minimum integer speed (in kilometers per hour) at which all the trains must travel to reach the office on time. If it is impossible, return -1.
Problem
Approach
Steps
Complexity
Input: The input consists of an integer array dist representing the distances for each train ride, and a floating-point number hour representing the total time to reach the office.
Example: [2, 5, 3], hour = 8
Constraints:
• 1 <= dist.length <= 10^5
• 1 <= dist[i] <= 10^5
• 1 <= hour <= 10^9
• hour has at most two decimal places.
Output: Return the minimum integer speed (in km/h) that all trains must travel to reach on time, or return -1 if it is impossible.
Example: 2
Constraints:
• The result should be an integer speed or -1.
Goal: The goal is to find the minimum integer speed that satisfies the given time constraint for all train rides.
Steps:
• Start with the smallest possible speed and calculate the time taken for each train ride.
• For each train ride, calculate the time based on the speed, and determine if you need to wait to depart at an integer hour.
• Use binary search to find the minimum speed that allows you to arrive at the office on time.
Goal: Constraints on the input values.
Steps:
• 1 <= dist.length <= 10^5
• 1 <= dist[i] <= 10^5
• 1 <= hour <= 10^9
• hour has at most two decimal places.
Assumptions:
• All the train distances are positive integers.
• The total time must be greater than or equal to the time required for each train ride.
• Input: [2, 5, 3], hour = 8
• Explanation: At speed 2, the time taken for each train ride ensures that you arrive exactly on time (8 hours).
• Input: [1, 5, 3], hour = 3.4
• Explanation: At speed 3, the total time is less than 3.4 hours, but it is impossible to make it on time as the total time is 3 hours.
Approach: The approach involves using binary search to find the minimum integer speed and ensuring the total travel time is within the given hour limit.
Observations:
• We need to handle the fractional times and wait for the next integer hour to depart for each train.
• Binary search on speed can help find the smallest feasible speed in an efficient manner.
Steps:
• Use binary search to find the minimum speed.
• For each potential speed, calculate the total time taken for all train rides.
• Return the smallest speed that allows you to reach on time, or -1 if none is found.
Empty Inputs:
• There are no empty inputs, as dist has at least one element.
Large Inputs:
• For large inputs, the binary search approach ensures efficiency within the constraints.
Special Values:
• Handle cases where hour is very small or very large, especially when it's impossible to make it on time.
Constraints:
• Ensure correct handling of fractional times due to non-integer hours.
bool canReach(int speed, vector<int>& dist, double hour) {
double est = 0;
for(int i = 0; i < dist.size(); i++) {
if(i == (dist.size() - 1)) est += (double)dist[i]/ speed;
else est = ceil(est + (double)dist[i]/ speed);
}
// cout << speed << " " << est << " " << (est <= hour) << "\n";
return est <= hour;
}
int minSpeedOnTime(vector<int>& dist, double hour) {
int l = 0, r = INT_MAX - 1;
int ans = INT_MAX;
while(l <= r) {
int speed = l + (r - l + 1)/2;
if(canReach(speed, dist, hour)) {
ans = speed;
r = speed - 1;
} else {
l = speed + 1;
}
}
return ans == INT_MAX? -1: ans;
}
1 : Helper Function
bool canReach(int speed, vector<int>& dist, double hour) {
Defines a helper function to check if the given speed allows reaching within the specified hour.
2 : Calculation
double est = 0;
Declares and initializes a variable to store the estimated time.
3 : For Loop
for(int i = 0; i < dist.size(); i++) {
Iterates through each distance segment to calculate time based on speed.
4 : Condition Check
if(i == (dist.size() - 1)) est += (double)dist[i]/ speed;
Checks if it's the last segment to compute exact travel time.
5 : Ceiling Calculation
else est = ceil(est + (double)dist[i]/ speed);
Adds the ceiling of travel time for intermediate segments.
6 : Return Statement
return est <= hour;
Returns true if the estimated time is within the allowed hour.
7 : Binary Search Initialization
int minSpeedOnTime(vector<int>& dist, double hour) {
Starts the function and initializes binary search bounds.
8 : Binary Search Initialization
int l = 0, r = INT_MAX - 1;
Defines the left and right bounds for binary search.
9 : Result Variable
int ans = INT_MAX;
Sets the result variable to track the minimum speed.
10 : While Loop
while(l <= r) {
Performs binary search to find the optimal speed.
11 : Midpoint Calculation
int speed = l + (r - l + 1)/2;
Calculates the midpoint speed for binary search.
12 : Valid Speed
if(canReach(speed, dist, hour)) {
Updates the result if the speed is valid.
13 : Update Right
ans = speed;
Updates the answer and adjusts the binary search bound.
14 : Update Right
r = speed - 1;
Adjusts the upper bound to refine the search.
15 : Else Block
} else {
Handles the case where speed is too low.
16 : Update Left
l = speed + 1;
Adjusts the lower bound to refine the search.
17 : Return Result
return ans == INT_MAX? -1: ans;
Returns the minimum speed or -1 if no valid speed exists.
Best Case: O(n log M), where M is the maximum possible speed (10^7).
Average Case: O(n log M), with n being the number of trains.
Worst Case: O(n log M), due to the binary search on speed and iterating over all train rides.
Description: The time complexity is logarithmic in terms of speed, with a linear scan of the train rides.
Best Case: O(1), no additional space is used beyond input and variables.
Worst Case: O(1), as we only use a few extra variables.
Description: The space complexity is constant.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus