parameters: (self, points, k)
return_statement: return left
docstring: :type points: List[List[int]]
          :type k: int
          :rtype: int
docstring_summary: :type points: List[List[int]]
          :type k: int
          :rtype: int
docstring_tokens: : type points : List [ List [ int ]] : type k : int : rtype : int
function: def minDayskVariants(self, points, k):
          """
          :type points: List[List[int]]
          :type k: int
          :rtype: int
          """
          def add_rec(rec, intervals):
              x0, y0, x1, y1 = rec
              # add [y0, y1] by 1 in [x0, x1+1)
              intervals.append([[x0,   +1], [y0, y1]])
              intervals.append([[x1+1, -1], [y0, y1]])
  
          def check(points, k, l):  # Time: O(nlogn), Space: O(n)
              intervals = []
              y_set = set()
              for x, y in points:
                  add_rec([x-l, y-l, x+l, y+l], intervals)
                  y_set.add(y-l)
                  y_set.add(y+l)
              intervals.sort()
              y_to_idx = {y:i for i, y in enumerate(sorted(y_set))}  # coordinate compression
              st = SegmentTree(len(y_to_idx))
              for [_, v], [y0, y1] in intervals:  # line sweep
                  st.update(y_to_idx[y0], y_to_idx[y1], v)
                  if st.query(0, len(y_to_idx)-1) >= k:
                      return True
              return False
                  
          points = [[x+y, x-y] for x, y in points]  # rotate
          min_x = min(points)[0]
          max_x = max(points)[0]
          min_y = min(points, key=lambda x: x[1])[1]
          max_y = max(points, key=lambda x: x[1])[1]
          left, right = 0, ((max_x-min_x)+(max_y-min_y)+1)//2
          while left <= right:
              mid = left + (right-left)//2
              if check(points, k, mid):
                  right = mid-1
              else:
                  left = mid+1
          return left
function_tokens: def minDayskVariants ( self , points , k ) : def add_rec ( rec , intervals ) : x0 , y0 , x1 , y1 = rec # add [y0, y1] by 1 in [x0, x1+1) intervals . append ( [ [ x0 , + 1 ] , [ y0 , y1 ] ] ) intervals . append ( [ [ x1 + 1 , - 1 ] , [ y0 , y1 ] ] ) def check ( points , k , l ) : # Time: O(nlogn), Space: O(n) intervals = [ ] y_set = set ( ) for x , y in points : add_rec ( [ x - l , y - l , x + l , y + l ] , intervals ) y_set . add ( y - l ) y_set . add ( y + l ) intervals . sort ( ) y_to_idx = { y : i for i , y in enumerate ( sorted ( y_set ) ) } # coordinate compression st = SegmentTree ( len ( y_to_idx ) ) for [ _ , v ] , [ y0 , y1 ] in intervals : # line sweep st . update ( y_to_idx [ y0 ] , y_to_idx [ y1 ] , v ) if st . query ( 0 , len ( y_to_idx ) - 1 ) >= k : return True return False points = [ [ x + y , x - y ] for x , y in points ] # rotate min_x = min ( points ) [ 0 ] max_x = max ( points ) [ 0 ] min_y = min ( points , key = lambda x : x [ 1 ] ) [ 1 ] max_y = max ( points , key = lambda x : x [ 1 ] ) [ 1 ] left , right = 0 , ( ( max_x - min_x ) + ( max_y - min_y ) + 1 ) // 2 while left <= right : mid = left + ( right - left ) // 2 if check ( points , k , mid ) : right = mid - 1 else : left = mid + 1 return left