Skip to content

3027. Find the Number of Ways to Place People II 👍

  • Time: $O(n^2)$
  • Space: $O(|\texttt{sort}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  // Same as 3025. Find the Number of Ways to Place People I
  int numberOfPairs(vector<vector<int>>& points) {
    int ans = 0;

    ranges::sort(points, [](const vector<int>& a, const vector<int>& b) {
      return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);
    });

    for (int i = 0; i < points.size(); ++i) {
      int maxY = INT_MIN;
      for (int j = i + 1; j < points.size(); ++j)
        if (points[i][1] >= points[j][1] && points[j][1] > maxY) {
          ++ans;
          maxY = points[j][1];
        }
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  // Same as 3025. Find the Number of Ways to Place People I
  public int numberOfPairs(int[][] points) {
    int ans = 0;

    Arrays.sort(points,
                (a, b) -> a[0] == b[0] ? Integer.compare(b[1], a[1]) : Integer.compare(a[0], b[0]));

    for (int i = 0; i < points.length; ++i) {
      int maxY = Integer.MIN_VALUE;
      for (int j = i + 1; j < points.length; ++j)
        if (points[i][1] >= points[j][1] && points[j][1] > maxY) {
          ++ans;
          maxY = points[j][1];
        }
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  # Same as 3025. Find the Number of Ways to Place People I
  def numberOfPairs(self, points: list[list[int]]) -> int:
    ans = 0

    points.sort(key=lambda x: (x[0], -x[1]))

    for i, (_, yi) in enumerate(points):
      maxY = -math.inf
      for j in range(i + 1, len(points)):
        _, yj = points[j]
        # Chisato is in the upper-left corner at (xi, yi), and Takina is in the
        # lower-right corner at (xj, yj). Also, if yj > maxY, it means that
        # nobody other than Chisato and Takina is inside or on the fence.
        if yi >= yj > maxY:
          ans += 1
          maxY = yj

    return ans