aboutsummaryrefslogtreecommitdiff
path: root/num_flower_bloom.c
blob: 16fc756f46e0f6ba0baa4e2293eac29090e4bb8d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
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;
}