You are given a floating-point number hour, representing the amount of time you have to reach the office. To commute to the office, you must take N trains in sequential order. You are also given an integer array dist of length N, where dist[i] describes the distance (in kilometers) of the ith train ride.
Each train can only depart at an integer hour, so you may need to wait in between each train ride. For example, if the 1st train ride takes 1.5 hours, you must wait for an additional 0.5 hours before you can depart on the 2nd train ride at the 2 hour mark. Return the minimum positive integer speed (in kilometers per hour) that all the trains must travel at for you to reach the office on time, or -1 if it is impossible to be on time.
Note: The test cases are guaranteed such that if a valid speed exists, it will never exceed 107 km/h. You can safely use 107 as the upper bound for your search.
Example 1
Input: dist = [1, 3, 2], hour = 6.0
Output: 1
Explanation: At speed 1:
The first train ride takes 1/1 = 1.0 hour.
Since we are already at an integer hour, we depart immediately at the 1 hour mark. The second train takes 3/1 = 3.0 hours.
We depart immediately at the 4 hour mark. The third train takes 2/1 = 2.0 hours.
You arrive at exactly the 6 hour mark.
Example 2
Input: dist = [1, 3, 2], hour = 1.9
Output: -1
Explanation: It is mathematically impossible because the earliest the third train can depart is at the 2 hour mark.
Brute Force Approach
The most direct idea is to try every possible speed. The smallest speed is 1. The problem uses 107 as the largest speed that needs to be checked. For each speed, calculate the total time needed to complete all train rides.
The important detail is how the time is calculated. Every train except the last one must use ceiling time because the next train starts only at an integer hour. The last train uses exact decimal time.
If speeds are checked from small to large, the first speed that reaches within hour is the minimum speed.
Algorithm
First, check whether
hour <= dist.length - 1. This is needed because the firstN - 1trains each need at least one full waiting slot, and the last train still needs some positive time.Try every speed from
1to 107. This checks possible speeds from smallest to largest.For each speed, calculate total travel time. Round up the time for every train except the last one because the next train can start only at an integer hour.
For the last train, add the exact decimal time because no more train has to be caught after it.
If the total time is less than or equal to
hour, return the current speed immediately because it is the first valid speed.If no speed works in the allowed range, return
-1.
Key Points
The last train is not rounded up.
The first
N - 1trains are rounded up because of integer-hour departure rules.If
hour <= N - 1, the answer is impossible.
Dry Run
Minimum Speed to Arrive on Time Brute Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: /* Calculates the total travel time needed for a given speed. */ double timeNeeded(vector<int>& dist, int speed) { int n = dist.size(); // This stores the total time for all train rides. double totalTime = 0.0; for (int i = 0; i < n; i++) { // The last train uses exact time // because there is no next train to wait for. if (i == n - 1) { totalTime += (double)dist[i] / speed; } else { // Earlier trains must round up // to the next integer departure hour. totalTime += ceil((double)dist[i] / speed); } } return totalTime; }public: /* Finds the minimum speed by checking all possible speeds one by one. */ int minSpeedOnTime(vector<int>& dist, double hour) { int n = dist.size(); // If even the waiting slots do not fit, // reaching on time is impossible. if (hour <= n - 1) { return -1; } for (int speed = 1; speed <= 10000000; speed++) { // The first speed that works is the answer // because speeds are checked from small to large. if (timeNeeded(dist, speed) <= hour) { return speed; } } return -1; }};// Driver code startsint main() { vector<int> dist = {1, 3, 2}; double hour = 2.7; Solution obj; cout << obj.minSpeedOnTime(dist, hour) << endl; return 0;}Complexity Analysis
Time Complexity: O(N x 107), because every possible speed, which may range up to 1e7, may check all train distances.
Space Complexity: O(1), because constant space is used.
Optimal Approach
The key observation is that speed controls the total travel time in one direction. If the speed is too slow, the train rides take too much time, so arriving within hour is impossible.
If the speed is fast enough, the travel time fits within hour. Any speed larger than that will also work because every train ride becomes shorter or stays rounded to the same integer hour.
So the possible speeds look like this: false, false, false, true, true, true
The answer is the first true, which means the smallest speed that reaches on time.
The rounding rule still matters during each check. Every train except the last one must be rounded up, while the last train uses exact decimal time.
Algorithm
First, check whether
hour <= N - 1. This is done because the firstN - 1train rides need at leastN - 1integer-hour slots, and the last ride still needs positive time.Set low to 1 because the speed must be a positive integer.
Set high to 107, which is the maximum speed that needs to be checked for this problem.
Pick the middle speed
midand calculate the total travel time at that speed.If the total time is less than or equal to
hour,midis valid. Movehightomidbecause a lower valid speed may still exist.Otherwise,
midis too slow. Movelowtomid + 1because all speeds up tomidcannot arrive on time.After the search ends, return
lowonly if that speed really works. Otherwise, return-1.
Dry Run
Minimum Speed to Arrive on Time Optimal Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: /* Calculates the total travel time needed for a given speed. */ double timeNeeded(vector<int>& dist, int speed) { int n = dist.size(); // This stores the total time for all train rides. double totalTime = 0.0; for (int i = 0; i < n; i++) { // The last train uses exact time // because there is no next train to wait for. if (i == n - 1) { totalTime += (double)dist[i] / speed; } else { // Earlier trains must round up // to the next integer departure hour. totalTime += ceil((double)dist[i] / speed); } } return totalTime; } /* Checks whether the chosen speed reaches the destination on time. */ bool canArrive(vector<int>& dist, int speed, double hour) { // The speed is valid only if total time fits within hour. return timeNeeded(dist, speed) <= hour; }public: /* Finds the minimum speed using binary search over all possible speed values. */ int minSpeedOnTime(vector<int>& dist, double hour) { int n = dist.size(); // If even the waiting slots do not fit, // reaching on time is impossible. if (hour <= n - 1) { return -1; } int low = 1; int high = 10000000; while (low < high) { // mid is the speed being tested right now. int mid = low + (high - low) / 2; // If mid works, try the left side for a smaller speed. if (canArrive(dist, mid, hour)) { high = mid; } else { // If mid fails, all smaller speeds fail too. low = mid + 1; } } // Return low only when it really reaches on time. if (canArrive(dist, low, hour)) { return low; } return -1; }};// Driver code startsint main() { vector<int> dist = {1, 3, 2}; double hour = 2.7; Solution obj; cout << obj.minSpeedOnTime(dist, hour) << endl; return 0;}Complexity Analysis
Time Complexity: O(N x log2(107)), because each binary-search check scans all train distances once, and binary search has an answer range of 1e7.
Space Complexity: O(1), because constant space is used.
Interview follow-up Questions
Every train ride forces you to wait until the next integer hour before taking the next one. This means 4 trains will mathematically take at least 3 hours just to clear the first 3 stops, regardless of how infinitely fast you travel. If the allowed hours are less than this minimum waiting baseline, it is completely impossible to arrive on time.
Be the first to add a comment.