• API
• FAQ
• Tools
• Archive
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.
Not a member of Pastebin yet?