diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /min_speed_arrive_time.c | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'min_speed_arrive_time.c')
-rw-r--r-- | min_speed_arrive_time.c | 44 |
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 +} |