C++ solution using reservoir sampling with explanation - concise and easy to understand
I found no other guys solved this problem using reservoir sampling method. Take a look at my solution.\n\n\nclass Solution {\npublic:\n    vector<vector<int>> r
I found no other guys solved this problem using reservoir sampling method. Take a look at my solution.\n\n```\nclass Solution {\npublic:\n    vector<vector<int>> rects;\n    \n    Solution(vector<vector<int>> rects) : rects(rects) {\n    }\n    \n    vector<int> pick() {\n        int sum_area = 0;\n        vector<int> selected;\n        \n        /* Step 1 - select a random rectangle considering the area of it. */\n        for (auto r : rects) {\n            /*\n             * What we need to be aware of here is that the input may contain\n             * lines that are not rectangles. For example, [1, 2, 1, 5], [3, 2, 3, -2].\n             * \n             * So, we work around it by adding +1 here. It does not affect\n             * the final result of reservoir sampling.\n             */\n            int area = (r[2] - r[0] + 1) * (r[3] - r[1] + 1);\n            sum_area += area;\n            \n            if (rand() % sum_area < area)\n                selected = r;\n        }\n        \n        /* Step 2 - select a random (x, y) coordinate within the selected rectangle. */\n        int x = rand() % (selected[2] - selected[0] + 1) + selected[0];\n        int y = rand() % (selected[3] - selected[1] + 1) + selected[1];\n        \n        return { x, y };\n    }\n};\n```\n\nThis problem is VERY BAD in the sense that the input actually contains something that is not a rectangle at all. It is different from what the title claims.\n\nIn the code above, reservoir sampling technique was used when we select a random rectangle in proportional to their area. Following resources will help you understand it:\n* https://en.wikipedia.org/wiki/Reservoir_sampling\n* https://www.youtube.com/watch?v=A1iwzSew5QY\n\n**However, using reservoir sampling may not be an optimal solution.** It is because of that picking a random rectangle by using reservoir sampling consumes high costs of O(n) time complexity each time, where n is the number of rectangles. So, overall time complexity goes up to O(nm), where m is the number of calls to pick(). On the other hand, its space complexity is O(1), because additional spaces are not required.\n\nAs other guys did, if we use binary search on the prefix sum of the weights, time complexity reduces to O(m log n), where m is the number of calls to pick() and n is the number of rectangles. However, its space complexity is O(n), requiring additional spaces for prefix sum of weight.
[]