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 /num_flower_bloom.c | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'num_flower_bloom.c')
-rw-r--r-- | num_flower_bloom.c | 55 |
1 files changed, 55 insertions, 0 deletions
diff --git a/num_flower_bloom.c b/num_flower_bloom.c new file mode 100644 index 0000000..16fc756 --- /dev/null +++ b/num_flower_bloom.c @@ -0,0 +1,55 @@ +// 2251. Number of Flowers in Full Bloom +#include <limits.h> +#include <stdlib.h> + +/* + * given a 0-indexed 2d integer array 'flowers', where 'flowers[i] = [start[i], + * end[i]]' means the i'th flower will be in full bloom from 'start[i]' to + * 'end[i]' (inclusive). you are also given a 0-indexed integer array 'people' + * of size 'n' where 'people[i]' is the time that the i'th person will arrive to + * see the flowers. return an integer array 'answer' of size 'n' where + * 'answer[i]' is the number of flowers that are in full bloom when the i'th + * person arrives. + */ + +struct pp { + int person; + int rank; +}; + +int cmp(const void *a, const void *b) { + return (*(struct pp *)a).person > (*(struct pp *)b).person ? 1 : -1; +} + +int *fullBloomFlowers(int **flowers, int flowers_size, int *flowers_col_size, + int *people, int people_size, int *return_size) { + *return_size = people_size; + int *ans = calloc(people_size, sizeof(int)), cnt = 0; + struct pp *list = malloc(sizeof(struct pp) * (people_size)); + struct pp *tree = malloc(sizeof(struct pp) * (flowers_size * 2 + 1)); + for (int i = 0; i < flowers_size; i++) { + tree[cnt].person = flowers[i][0]; + tree[cnt].rank = 1; + cnt++; + tree[cnt].person = flowers[i][1] + 1; + tree[cnt].rank = -1; + cnt++; + } + for (int i = 0; i < people_size; i++) { + list[i].person = people[i]; + list[i].rank = i; + } + qsort(tree, flowers_size * 2, sizeof(struct pp), cmp); + qsort(list, people_size, sizeof(struct pp), cmp); + tree[cnt].person = INT_MAX; + int now = 0, flower = 0; + for (int i = 0; i < people_size; i++) { + while (list[i].person >= tree[now].person) { + flower += tree[now].rank; + now++; + } + ans[list[i].rank] = flower; + } + free(list), free(tree); + return ans; +} |