diff options
Diffstat (limited to 'other/min_speed_arrive_time.cpp')
-rw-r--r-- | other/min_speed_arrive_time.cpp | 47 |
1 files changed, 0 insertions, 47 deletions
diff --git a/other/min_speed_arrive_time.cpp b/other/min_speed_arrive_time.cpp deleted file mode 100644 index 55cfa98..0000000 --- a/other/min_speed_arrive_time.cpp +++ /dev/null @@ -1,47 +0,0 @@ -// 1870. Minimum Speed to Arrive on Time -#include "leetcode.h" - -/* - * 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 kilometres of the i'th train ride. - * each train can only depart at an integer hour, so you may need to wait in - * between each ride. return the minimum number speed in km/h that all the - * trains must travel at for you to reach the office on time, or '-1' if it is - * possible to be on time. - */ - -class Solution { - bool can_reach_on_time(vector<int> &dist, double hour, int speed) { - double time = 0; - for (int i = 0; i < dist.size() - 1; ++i) - time += ((dist[i] + speed - 1) / speed); - time += ((double)dist.back()) / speed; - return time <= hour; - } - -public: - int minSpeedOnTime(vector<int> dist, double hour) { - int n = dist.size(); - if (hour <= n - 1) - return -1; - int low = 1, high = 1e7, mid; - while (low < high) { - mid = (low + high) / 2; - if (can_reach_on_time(dist, hour, mid)) - high = mid; - else - low = mid + 1; - } - return high; - } -}; - -int main() { - Solution obj; - vector<int> dist = {1, 3, 2}; - printf("%d\n", obj.minSpeedOnTime(dist, 6)); // expect: 1 - printf("%d\n", obj.minSpeedOnTime(dist, 2.7)); // expect: 3 - printf("%d\n", obj.minSpeedOnTime(dist, 1.9)); // expect: -1 -} |