aboutsummaryrefslogtreecommitdiff
path: root/min_speed_arrive_time.c
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /min_speed_arrive_time.c
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'min_speed_arrive_time.c')
-rw-r--r--min_speed_arrive_time.c44
1 files changed, 44 insertions, 0 deletions
diff --git a/min_speed_arrive_time.c b/min_speed_arrive_time.c
new file mode 100644
index 0000000..421093c
--- /dev/null
+++ b/min_speed_arrive_time.c
@@ -0,0 +1,44 @@
+// 1870. Minimum Speed to Arrive on Time
+#include <math.h>
+#include <stdio.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.
+ */
+
+double hours(int *dist, int dist_size, double hour) {
+ double res = 0;
+ for (int i = 0; i < dist_size - 1; i++)
+ res += ceil(1.0 * dist[i] / hour);
+ res += (((double)dist[dist_size - 1]) / hour);
+ return res;
+}
+
+int minSpeedOnTime(int *dist, int dist_size, double hour) {
+ if (hour <= dist_size - 1)
+ return -1;
+ int left = 1, right = 1e7, mid, ans;
+ while (left < right) {
+ mid = (left + right) / 2;
+ if (hours(dist, dist_size, mid) <= hour) {
+ right = mid;
+ ans = mid;
+ } else
+ left = mid + 1;
+ }
+ return ans;
+}
+
+int main() {
+ int dist[] = {1, 3, 2}, dist_size = 3;
+ printf("%d\n", minSpeedOnTime(dist, dist_size, 6)); // expect: 1
+ printf("%d\n", minSpeedOnTime(dist, dist_size, 2.7)); // expect: 6
+ printf("%d\n", minSpeedOnTime(dist, dist_size, 1.9)); // expect: -1
+}