diff options
-rw-r--r-- | find_num_ways_place_people2.c | 59 | ||||
-rw-r--r-- | find_num_ways_place_people2.py | 40 |
2 files changed, 99 insertions, 0 deletions
diff --git a/find_num_ways_place_people2.c b/find_num_ways_place_people2.c new file mode 100644 index 0000000..771d94a --- /dev/null +++ b/find_num_ways_place_people2.c @@ -0,0 +1,59 @@ +// 3027. Find the Number of Ways to Place People II +#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]'. we + * define the right direction as positive x-axis and the left direction as + * negative x-axis. similarly, up and down are postive and negative y-axis + * accordingly. you have to place 'n' people including alice and bob at these + * points such that there is exactly one person at every point. alice wants to + * be alone with bob, so alice will build a rectangular fence with alice's + * position as the upper left corner and bob's position as the lower right + * corner + */ + +int cmp(const void *a, const void *b) { + const int *aa = *(const int **)a; + const int *bb = *(const int **)b; + return aa[0] == bb[0] ? aa[1] - bb[1] : bb[0] - aa[0]; +} + +int numberOfPairs(int **points, int pointsSize, int *pointsColSize) { + int ans = 0; + qsort(points, pointsSize, sizeof(int *), cmp); + for (int i = 0; i < pointsSize - 1; i++) { + int y = INT_MAX, yi = points[i][1]; + for (int j = i + 1; j < pointsSize; j++) { + const int yj = points[j][1]; + if (yj >= yi && y > j) { + ans++; + y = yj; + if (yi == yj) + break; + } + } + } + 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); +} diff --git a/find_num_ways_place_people2.py b/find_num_ways_place_people2.py new file mode 100644 index 0000000..15d5205 --- /dev/null +++ b/find_num_ways_place_people2.py @@ -0,0 +1,40 @@ +# 3027. Find the Number of Ways to Place People II + +""" +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]'. we +define the right direction as positive x-axis and the left direction as +negative x-axis. similarly, up and down are postive and negative y-axis +accordingly. you have to place 'n' people including alice and bob at these +points such that there is exactly one person at every point. alice wants to +be alone with bob, so alice will build a rectangular fence with alice's +position as the upper left corner and bob's position as the lower right +corner +""" + + +class Solution(object): + def numberOfPairs(self, points): + """ + :type points: List[List[int]] + :rtype: int + """ + points.sort(key=lambda x: (-x[0], x[1])) + ans, n = 0, len(points) + for i in range(n - 1): + y, yi = float("inf"), points[i][1] + for j in range(i + 1, n): + yj = points[j][1] + if y > yj >= yi: + ans += 1 + y = yj + if yi == yj: + break + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.numberOfPairs(points=[[1, 1], [2, 2], [3, 3]])) + print(obj.numberOfPairs(points=[[6, 2], [4, 4], [2, 6]])) + print(obj.numberOfPairs(points=[[3, 1], [1, 3], [1, 1]])) |