cmiN

disk-space.py

Nov 22nd, 2020
430
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import bisect
  2. from collections import deque
  3.  
  4.  
  5. def comp_space(x, space):
  6.     sub = space[:x]
  7.     rng = deque(sub)
  8.     sub.sort()
  9.     max_space = 0
  10.     idx = x
  11.     length = len(space)
  12.  
  13.     # Now the entire loop should be of O(NlogN).
  14.     while True:
  15.         min_space = sub[0]  # O(1)
  16.         if min_space > max_space:
  17.             max_space = min_space
  18.  
  19.         if idx >= length:
  20.             break
  21.  
  22.         # BEGIN O(1)
  23.         rem_elem = rng.popleft()
  24.         add_elem = space[idx]
  25.         rng.append(add_elem)
  26.         # END O(1)
  27.  
  28.         # BEGIN O(logN)
  29.         pos = bisect.bisect_left(sub, rem_elem)
  30.         sub.pop(pos)  # This might slow down to O(N)
  31.         bisect.insort_left(sub, add_elem)
  32.         # END O(logN)
  33.  
  34.         idx += 1
  35.  
  36.     return max_space
  37.  
  38.  
  39. if __name__ == "__main__":
  40.     assert comp_space(3, [2, 4, 6, 8, 5]) == 5
  41.  
RAW Paste Data