c++ simple solution by transfering all 2D rectangles to a 1D line
My idea is to transfer all rectangles to a 1D line, then random pick up one point from the line. Finally convert the point in the line back to its\' real positi
My idea is to transfer all rectangles to a 1D line, then random pick up one point from the line. Finally convert the point in the line back to its\' real position. \n```\nclass Solution {\npublic:\n    map<int,int> toRect;\n    vector<vector<int>> rs;\n    int total = 0;\n    Solution(vector<vector<int>>& rects) : rs(rects){\n        toRect[0] = 0;\n        for(int i = 0;i<rs.size();i++){\n            auto& x = rs[i];\n            int area = (x[2] - x[0] + 1) * (x[3] - x[1] + 1);\n            total += area;\n            toRect[total] = i+1;\n        }\n    }\n    \n    vector<int> f(const vector<int>& r, int i){\n        int width = r[2] - r[0] + 1;\n        int _x = i % width;\n        int _y = i / width; \n        return {r[0] + _x, r[1] + _y};\n    }\n    \n    vector<int> pick() {\n        int r = rand() % total;\n        auto ptr = toRect.upper_bound(r);\n        ptr = next(ptr,-1);\n        return f(rs[ptr->second],r - ptr->first);\n    }\n};\n```
[]