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 /boats_save_people.c | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'boats_save_people.c')
-rw-r--r-- | boats_save_people.c | 34 |
1 files changed, 34 insertions, 0 deletions
diff --git a/boats_save_people.c b/boats_save_people.c new file mode 100644 index 0000000..d0cb7f4 --- /dev/null +++ b/boats_save_people.c @@ -0,0 +1,34 @@ +// 881. Boats to Save People +#include <stdio.h> +#include <stdlib.h> + +/* + * given an array 'people' where 'people[i]' is the weight of the i'th person, + * and an infinite number of boats where each boat can carry a maximum weight of + * 'limit'. each boat carries at most two people at the same time, provided the + * sum of the weight of those people is at most 'limit'. return minimum number + * of boats to carry every person + */ + +int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; } + +int numRescueBoats(int *people, int people_size, int limit) { + qsort(people, people_size, sizeof(int), cmp); + int max_weight = people_size - 1, min_weight = 0, ans = 0; + while (min_weight <= max_weight) { + if (people[min_weight] + people[max_weight] <= limit) { + min_weight++; + max_weight--; + } else + max_weight--; + ans++; + } + return ans; +} + +int main() { + int p1[] = {1, 2}, p2[] = {3, 2, 2, 1}, p3[] = {3, 5, 3, 4}; + printf("%d\n", numRescueBoats(p1, 2, 3)); // expect: 1 + printf("%d\n", numRescueBoats(p2, 4, 3)); // expect: 3 + printf("%d\n", numRescueBoats(p3, 4, 5)); // expect: 4 +} |