aboutsummaryrefslogtreecommitdiff
path: root/min_speed_arrive_time.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'min_speed_arrive_time.cpp')
-rw-r--r--min_speed_arrive_time.cpp47
1 files changed, 47 insertions, 0 deletions
diff --git a/min_speed_arrive_time.cpp b/min_speed_arrive_time.cpp
new file mode 100644
index 0000000..55cfa98
--- /dev/null
+++ b/min_speed_arrive_time.cpp
@@ -0,0 +1,47 @@
+// 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
+}