diff options
author | Jack Sangdahl <[email protected]> | 2025-09-01 22:15:45 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-09-01 22:15:45 -0600 |
commit | 57914ff67da704020301e06ab036c92c81ee85ab (patch) | |
tree | 1093b89f2b2e5d8db68b8bb1fc2702ac3bbe7984 /find_num_place_people1.c | |
parent | 926cb9384bf3b282310688d247cc245a444e62d4 (diff) | |
download | leetcode-57914ff67da704020301e06ab036c92c81ee85ab.tar.gz leetcode-57914ff67da704020301e06ab036c92c81ee85ab.zip |
3025. find the number of ways to place people 1
Diffstat (limited to 'find_num_place_people1.c')
-rw-r--r-- | find_num_place_people1.c | 62 |
1 files changed, 62 insertions, 0 deletions
diff --git a/find_num_place_people1.c b/find_num_place_people1.c new file mode 100644 index 0000000..d51a81b --- /dev/null +++ b/find_num_place_people1.c @@ -0,0 +1,62 @@ +// 3025. Find the Number of Ways to Place People I +#include "leetcode.h" + +/* + * you are given a 2d array 'points' of size 'n x 2' representing integer + * coordinates of some points on a 2d plane, where 'points[i] = [x_i, y_i]'. + * count the number of pairs of points '(a, b)' where 'a' is on the upper left + * side of 'b' and there are no other points in the rectangle they make, + * including the border. return the count. + */ + +struct pair { + int x; + int y; +}; + +int cmp(const void *a, const void *b) { + struct pair *aa = (struct pair *)a, *bb = (struct pair *)b; + return aa->x != bb->x ? aa->x - bb->x : bb->y - aa->y; +} + +int numberOfPairs(int **points, int pointsSize, int *pointsColSize) { + int i, j, y, ans = 0; + struct pair *list = (struct pair *)malloc(pointsSize * sizeof(struct pair)); + for (int i = 0; i < pointsSize; i++) { + list[i].x = points[i][0]; + list[i].y = points[i][1]; + } + qsort(list, pointsSize, sizeof(struct pair), cmp); + for (int i = 0; i < pointsSize; i++) { + int y = INT_MIN; + for (int j = i + 1; j < pointsSize; j++) { + if (list[i].y >= list[j].y && y < list[j].y) { + ans++; + y = list[j].y; + } + } + } + free(list); + return ans; +} + +int main() { + int p1i[3][2] = {{1, 1}, {2, 2}, {3, 3}}, + p2i[3][2] = {{6, 2}, {4, 4}, {2, 6}}, + p3i[3][2] = {{3, 1}, {1, 3}, {1, 1}}; + struct two_d_arr *p1 = + two_d_arr_init(ARRAY_SIZE(p1i), ARRAY_SIZE(p1i[0]), p1i); + struct two_d_arr *p2 = + two_d_arr_init(ARRAY_SIZE(p2i), ARRAY_SIZE(p2i[0]), p2i); + struct two_d_arr *p3 = + two_d_arr_init(ARRAY_SIZE(p3i), ARRAY_SIZE(p3i[0]), p3i); + printf("%d\n", + numberOfPairs(p1->arr, p1->row_size, p1->col_size)); // expect: 0 + printf("%d\n", + numberOfPairs(p2->arr, p2->row_size, p2->col_size)); // expect: 2 + printf("%d\n", + numberOfPairs(p3->arr, p3->row_size, p3->col_size)); // expect: 2 + two_d_arr_free(p1); + two_d_arr_free(p2); + two_d_arr_free(p3); +} |