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 /latest_time_catch_bus.c | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'latest_time_catch_bus.c')
-rw-r--r-- | latest_time_catch_bus.c | 48 |
1 files changed, 48 insertions, 0 deletions
diff --git a/latest_time_catch_bus.c b/latest_time_catch_bus.c new file mode 100644 index 0000000..0f280d6 --- /dev/null +++ b/latest_time_catch_bus.c @@ -0,0 +1,48 @@ +// 2332. The Latest Time to Catch a Bus +#include "leetcode.h" + +/* + * given a 0-indexed array 'buses' of length 'n' where 'buses[i]' represents the + * departure time of the i'th bus. you are also given a 0-indexed array + * 'passengers' of length 'm' where 'passengers[j]' represents the arrival time + * of the j'th passenger. all bus departure times are unique. all passenger + * arrival times are unique. return the latest time you may arrive at the bus + * station to catch a bus. you cannot arrive at the same time as another + * passenger. + */ + +int cmp(const void *a, const void *b) { + if (*(int *)a == *(int *)b) + return 0; + return *(int *)a < *(int *)b ? -1 : 1; +} + +int latestTimeCatchTheBus(int *buses, int busesSize, int *passengers, + int passengersSize, int capacity) { + qsort(buses, busesSize, sizeof(int), cmp); + qsort(passengers, passengersSize, sizeof(int), cmp); + int p = 0, last_board = -1, last_bus = busesSize - 1, j; + for (int i = 0; i < busesSize; i++) + for (j = 0; j < capacity && p < passengersSize && passengers[p] <= buses[i]; + j++) { + last_board = i; + p++; + } + if (last_board != last_bus) + return buses[last_bus]; + p--; + if (j < capacity && passengers[p] + 1 <= buses[last_board]) + return buses[last_board]; + while (p && passengers[p] - 1 == passengers[p - 1]) + p--; + return passengers[p] - 1; +} + +int main() { + int b1[] = {10, 20}, p1[] = {2, 17, 18, 19}, b2[] = {20, 30, 10}, + p2[] = {19, 13, 26, 4, 25, 11, 21}; + printf("%d\n", latestTimeCatchTheBus(b1, ARRAY_SIZE(b1), p1, ARRAY_SIZE(p1), + 2)); // expect: 16 + printf("%d\n", latestTimeCatchTheBus(b2, ARRAY_SIZE(b2), p2, ARRAY_SIZE(p2), + 2)); // expect: 20 +} |