Advertisement
hoangreal

Max number of non-overlapping, L or R, pins visible

Oct 21st, 2024
52
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.65 KB | None | 0 0
  1. """
  2. Pinterest app screen is two columns of images (pins).
  3. Each pin has a top and bottom index (top < bottom), and has a column represented by "L" or "R".
  4. Given an unsorted list of non-overlapping pins like
  5.  
  6. pins = [(top_ind,bottom_ind,column),...,]
  7. and a screen_length of screen_len
  8. Return the maximum number of pins the user can possibly see (fully).
  9. """
  10.  
  11. def solve(pins,screen_len):
  12.     """
  13.    pin on left or right does not matter since
  14.    there are no overlaps for the pins on each side of column, we do not need to separate it
  15.    """
  16.     # Sort pins by bottom index in ascending order
  17.     pins = sorted(pins, key=lambda p: p[1])
  18.    
  19.     # Bottom of the sliding window
  20.     window_bot = screen_len
  21.    
  22.     # The most we need to check is max(screen_len, max of the last pin bot)
  23.     max_bot = max(screen_len, max([p[1] for p in pins]))
  24.    
  25.     fitted_pins, max_pins = [], 0
  26.     while window_bot <= max_bot:
  27.         window_top = window_bot - screen_len
  28.  
  29.         # Remove all fitted pins that have now exited the current window, realistically this should only run at most 2 times since
  30.         # we are sliding the window 1 frame at a time and there are 2 columns
  31.         while fitted_pins and (fitted_pins[0][0] < window_top or fitted_pins[0][1] > window_bot):
  32.             fitted_pins.pop(0)
  33.  
  34.         # Add all pins that fit the current window, again realistically this should only run at most 2 times, 1 for each column
  35.         while pins and (pins[0][0] >= window_top and pins[0][1] <= window_bot):
  36.             fitted_pins.append(pins.pop(0))
  37.             max_pins = max(max_pins, len(fitted_pins))
  38.         window_bot += 1
  39.  
  40.     return max_pins
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement