@@ -0,0 +1,2263 @@
+# Time:  O(logn)%0A# Space: O(n)%0A%0A# Given a list of non-overlapping axis-aligned rectangles rects,%0A# write a function pick which randomly and uniformily picks%0A# an integer point in the space covered by the rectangles.%0A#%0A# Note:%0A# - An integer point is a point that has integer coordinates. %0A# - A point on the perimeter of a rectangle is included in the space covered by the rectangles. %0A# - ith rectangle = rects%5Bi%5D = %5Bx1,y1,x2,y2%5D,%0A#   where %5Bx1, y1%5D are the integer coordinates of the bottom-left corner,%0A#   and %5Bx2, y2%5D are the integer coordinates of the top-right corner.%0A# - length and width of each rectangle does not exceed 2000.%0A# - 1 %3C= rects.length %3C= 100%0A# - pick return a point as an array of integer coordinates %5Bp_x, p_y%5D%0A# - pick is called at most 10000 times.%0A#%0A# Example 1:%0A#%0A# Input: %0A# %5B%22Solution%22,%22pick%22,%22pick%22,%22pick%22%5D%0A# %5B%5B%5B%5B1,1,5,5%5D%5D%5D,%5B%5D,%5B%5D,%5B%5D%5D%0A# Output: %0A# %5Bnull,%5B4,1%5D,%5B4,1%5D,%5B3,3%5D%5D%0A# Example 2:%0A#%0A# Input: %0A# %5B%22Solution%22,%22pick%22,%22pick%22,%22pick%22,%22pick%22,%22pick%22%5D%0A# %5B%5B%5B%5B-2,-2,-1,-1%5D,%5B1,0,3,0%5D%5D%5D,%5B%5D,%5B%5D,%5B%5D,%5B%5D,%5B%5D%5D%0A# Output: %0A# %5Bnull,%5B-1,-2%5D,%5B2,0%5D,%5B-2,-1%5D,%5B3,0%5D,%5B-2,-2%5D%5D%0A# Explanation of Input Syntax:%0A#%0A# The input is two lists: the subroutines called and their arguments.%0A# Solution's constructor has one argument,%0A# the array of rectangles rects. pick has no arguments.%0A# Arguments are always wrapped with a list, even if there aren't any.%0A%0Aimport random%0Aimport bisect%0A%0A%0Aclass Solution(object):%0A%0A    def __init__(self, rects):%0A        %22%22%22%0A        :type rects: List%5BList%5Bint%5D%5D%0A        %22%22%22%0A        self.__rects = list(rects)%0A        self.__prefix_sum = map(lambda x : (x%5B2%5D-x%5B0%5D+1)*(x%5B3%5D-x%5B1%5D+1), rects)%0A        for i in xrange(1, len(self.__prefix_sum)):%0A            self.__prefix_sum%5Bi%5D += self.__prefix_sum%5Bi-1%5D%0A%0A    def pick(self):%0A        %22%22%22%0A        :rtype: List%5Bint%5D%0A        %22%22%22%0A        target = random.randint(0, self.__prefix_sum%5B-1%5D-1)%0A        left = bisect.bisect_right(self.__prefix_sum, target)%0A        rect = self.__rects%5Bleft%5D%0A        width = rect%5B2%5D-rect%5B0%5D+1%0A        height = rect%5B3%5D-rect%5B1%5D+1%0A        base = self.__prefix_sum%5Bleft%5D-width*height%0A        return %5Brect%5B0%5D+(target-base)%25width, rect%5B1%5D+(target-base)//width%5D%0A%0A%0A# Your Solution object will be instantiated and called as such:%0A# obj = Solution(rects)%0A# param_1 = obj.pick()%0A

Create random-point-in-non-overlapping-rectangles.py