2250. Count Number of Rectangles Containing Each Point

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> countRectangles(vector<vector<int>>& rectangles, vector<vector<int>>& points) {
        // TLE, O(nm)
        vector<int> ret;
        for(auto p:points){
            int count = 0;
            for(auto r:rectangles){
                if(p[0]<=r[0] && p[1]<=r[1]) count++;
            }
            ret.push_back(count);
        }
        return ret;
    }
};

option 1

Sort the rectangles at each height and use binary search.

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:
    vector<int> countRectangles(vector<vector<int>>& rectangles, vector<vector<int>>& points) {
        int n(size(rectangles)), maxy(0);
        for (auto& r : rectangles)   maxy = max(maxy, r[1]);
        vector<int> ls[maxy + 1];
        // vector<vector<int>> ls(maxy+1);
        for (auto& r : rectangles)  ls[r[1]].push_back(r[0]);
        for(int y = 0; y <= maxy; ++y)  sort(ls[y].begin(), ls[y].end());
        vector<int> ret;
        for(auto p:points){
            int res = 0;
            for (int y=p[1]; y<=maxy; ++y) {
                auto cnt = ls[y].end() - lower_bound(ls[y].begin(), ls[y].end(), p[0]);
                res += cnt;
            }
            ret.push_back(res);

        }
        return ret;
    }
};

analysis

  • time complexity O(nlogm)
  • space complexity O(nm)