Skip to content

Find the Number of Ways to Place People I⚓︎

Link

3027: Find the Number of Ways to Place People II is the same question.

Solution⚓︎

 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:
    int numberOfPairs(vector<vector<int>>& points) {
        sort(points.begin(), points.end(), [](const auto& p, const auto& q) {
            return p[0] != q[0] ? (p[0] < q[0]) : (p[1] > q[1]);
        });

        int res = 0, n = points.size();
        for (int i = 0; i < n; i++) {
            int y0 = points[i][1];
            int maxY = INT_MIN;
            for (int j = i + 1; j < n; j++) {
                int y = points[j][1];
                if (y <= y0 && y > maxY) {
                    maxY = y;
                    res++;
                }
            }
        }
        return res;
    }
};
  • Time complexity: \(O(n^2)\);
  • Space complexity: \(O(1)\).