#3027
Find the Number of Ways to Place People II
expert · 1110 · lc hard +32 · verified · 64.4% accepted · 357 likes · top 68%
Description
You are given a 2D array points of size n x 2 of integer coordinates.
Place n people (including Alice and Bob) at these points, one per point. Alice builds a rectangular fence with her position as the upper-left corner and Bob's as the lower-right corner. Alice is unhappy if anyone else is inside or on the fence.
Return the number of (Alice, Bob) point pairs where Alice stays happy.
Note: Alice must be upper-left and Bob lower-right.
Example 1:
Input: points = [[1,1],[2,2],[3,3]]
Output: 0
Explanation: There is no way to place Alice and Bob such that Alice can build a fence with Alice's position as the upper left corner and Bob's position as the lower right corner. Hence we return 0.
Example 2:
Input: points = [[6,2],[4,4],[2,6]]
Output: 2
Explanation: There are two ways to place Alice and Bob such that Alice will not be sad:
- Place Alice at (4, 4) and Bob at (6, 2).
- Place Alice at (2, 6) and Bob at (4, 4).
You cannot place Alice at (2, 6) and Bob at (6, 2) because the person at (4, 4) will be inside the fence.
Example 3:
Input: points = [[3,1],[1,3],[1,1]]
Output: 2
Explanation: There are two ways to place Alice and Bob such that Alice will not be sad:
- Place Alice at (1, 1) and Bob at (3, 1).
- Place Alice at (1, 3) and Bob at (1, 1).
You cannot place Alice at (1, 3) and Bob at (3, 1) because the person at (1, 1) will be on the fence.
Note that it does not matter if the fence encloses any area, the first and second fences in the image are valid.
Code
1
2
3