From d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa Mon Sep 17 00:00:00 2001 From: jack <0x6A73@pm.me> Date: Fri, 14 Jun 2024 13:13:15 -0600 Subject: initial --- num_flower_bloom.c | 55 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 55 insertions(+) create mode 100644 num_flower_bloom.c (limited to 'num_flower_bloom.c') 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 +#include + +/* + * 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; +} -- cgit v1.2.3