{"id":3342,"date":"2018-07-28T17:45:20","date_gmt":"2018-07-29T00:45:20","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=3342"},"modified":"2018-07-28T17:52:58","modified_gmt":"2018-07-29T00:52:58","slug":"leetcode-882-random-point-in-non-overlapping-rectangles","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/geometry\/leetcode-882-random-point-in-non-overlapping-rectangles\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 882. Random Point in Non-overlapping Rectangles"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

Given a list of\u00a0non-overlapping<\/strong>\u00a0axis-aligned rectangles\u00a0rects<\/code>, write a function\u00a0pick<\/code>\u00a0which randomly and uniformily picks an\u00a0integer point<\/strong>\u00a0in the space\u00a0covered by the rectangles.<\/p>\n

Note:<\/p>\n

    \n
  1. An\u00a0integer point<\/strong>\u00a0is a point that has integer coordinates.<\/li>\n
  2. A point\u00a0on the perimeter\u00a0of a rectangle is\u00a0included<\/strong>\u00a0in the space covered by the rectangles.<\/li>\n
  3. i<\/code>th rectangle =\u00a0rects[i]<\/code>\u00a0=\u00a0[x1,y1,x2,y2]<\/code>, where\u00a0[x1, y1]<\/code>\u00a0are the integer coordinates of the bottom-left corner, and\u00a0[x2, y2]<\/code>\u00a0are the integer coordinates of the top-right corner.<\/li>\n
  4. length and width of each rectangle does not exceed\u00a02000<\/code>.<\/li>\n
  5. 1 <= rects.length\u00a0<= 100<\/code><\/li>\n
  6. pick<\/code>\u00a0return a point as an array of integer coordinates\u00a0[p_x, p_y]<\/code><\/li>\n
  7. pick<\/code>\u00a0is called at most\u00a010000<\/code>\u00a0times.<\/li>\n<\/ol>\n
    \n

    Example 1:<\/strong><\/p>\n

    Input: \r\n<\/strong>[\"Solution\",\"pick\",\"pick\",\"pick\"]\r\n<\/span>[[[[1,1,5,5]]],[],[],[]]<\/span>\r\nOutput: \r\n<\/strong>[null,[4,1],[4,1],[3,3]]<\/span>\r\n<\/pre>\n
    \n
    Example 2:<\/strong><\/p>\n
    Input: \r\n<\/strong>[\"Solution\",\"pick\",\"pick\",\"pick\",\"pick\",\"pick\"]\r\n<\/span>[[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]<\/span>\r\nOutput: \r\n<\/strong>[null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]]<\/span><\/pre>\n<\/div>\n
    \n
    Explanation of Input Syntax:<\/strong><\/p>\n
    The input is two lists:\u00a0the subroutines called\u00a0and their\u00a0arguments.\u00a0Solution<\/code>‘s\u00a0constructor has one argument, the array of rectangles\u00a0rects<\/code>.\u00a0pick<\/code>\u00a0has no arguments.\u00a0Arguments\u00a0are\u00a0always wrapped with a list, even if there aren’t any.<\/p>\n<\/div>\n
    Solution: Binary Search<\/strong><\/h1>\n
    Same as\u00a0LeetCode 880. Random Pick with Weight<\/a><\/p>\n
    Use area of the rectangles as weights.<\/p>\n
    Time complexity: Init: O(n) Pick: O(logn)<\/p>\n
    Space complexity: O(n)<\/p>\n
    \/\/ Author: Huahua\r\n\/\/ Running time: 92 ms\r\nclass Solution {\r\npublic:\r\n  Solution(vector<vector<int>> rects): rects_(std::move(rects)) {\r\n    sums_ = vector<int>(rects_.size());\r\n    for (int i = 0; i < rects_.size(); ++i) {\r\n      sums_[i] = (rects_[i][2] - rects_[i][0] + 1) * (rects_[i][3] - rects_[i][1] + 1);\r\n      if (i > 0) sums_[i] += sums_[i - 1];\r\n    }\r\n  }\r\n\r\n  vector<int> pick() {\r\n    const int s = nextInt(sums_.back()) + 1;\r\n    int index = lower_bound(sums_.begin(), sums_.end(), s) - sums_.begin();\r\n    const auto& rect = rects_[index];\r\n    return {rect[0] + nextInt(rect[2] - rect[0] + 1),\r\n            rect[1] + nextInt(rect[3] - rect[1] + 1)};\r\n  }\r\n    \r\nprivate:  \r\n  vector<int> sums_;\r\n  vector<vector<int>> rects_;\r\n  \r\n  \/\/ Returns a random int in [0, n - 1]\r\n  int nextInt(int n) {\r\n    return rand() \/ static_cast<double>(RAND_MAX) * n;\r\n  }\r\n};<\/pre>\n
    Related Problems<\/strong><\/h1>\n