SHARE
TWEET

Untitled

a guest May 24th, 2019 81 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution:
  2.     def __init__(self, N):
  3.         self.n = N
  4.  
  5.         # Auxilary DS to store left/right occupied room for a given occupied room
  6.         # Useful in updating heap when book() or leave() is called
  7.         self.left_occupied = {}
  8.         self.right_occupied = {}
  9.  
  10.         # root element stores longest free range of rooms
  11.         # maybe we need custom key to order heap elements
  12.         # element is of form { left_occupied: a, right_occupied: b }
  13.         self._heap = []
  14.    
  15.     def find_place(self):
  16.         '''
  17.         O(1) look up from top of heap
  18.         '''
  19.         optimal_slot = self._heap.top()
  20.         l, r = optimal_slot.left_occupied, optimal_slot.right_occupied
  21.         if abs(r - l) < 1: return -1
  22.         return (r + l + 1) // 2
  23.    
  24.     def book(self, a):
  25.         '''
  26.         O(logN) for heap push (heapify OP)
  27.         Assuming a is most optimal available room
  28.         pick most optimal room from top of heap and update heap
  29.         '''
  30.         optimal_slot = self._heap.pop()
  31.         l, r = optimal_slot.left_occupied, optimal_slot.right_occupied
  32.         self.left_occupied[a] = l
  33.         self.right_occupied[a] = r
  34.  
  35.         self.left_occupied[r] = self.right_occupied[l] = a
  36.         self._heap.push({
  37.             'left_occupied': l,
  38.             'right_occupied': a,
  39.         })
  40.         self._heap.push({
  41.             'left_occupied': a,
  42.             'right_occupied': r,
  43.         })
  44.         # TODO
  45.         # Need to remove [l, r] range from heap
  46.    
  47.     def leave(self, a):
  48.         '''
  49.         O(logN) for heap push (heapify OP)
  50.         return nil if a is not occupied currently
  51.         '''
  52.         if a not in self.left_occupied: return
  53.         l, r = self.left_occupied[a], self.right_occupied[a]
  54.         self._heap.push({
  55.             'left_occupied': l,
  56.             'right_occupied': r,
  57.         })
  58.         # TODO
  59.         # Needs to remove [l, a] and [a, r] ranges from heap
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top