Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- """
- Pinterest app screen is two columns of images (pins).
- Each pin has a top and bottom index (top < bottom), and has a column represented by "L" or "R".
- Given an unsorted list of non-overlapping pins like
- pins = [(top_ind,bottom_ind,column),...,]
- and a screen_length of screen_len
- Return the maximum number of pins the user can possibly see (fully).
- """
- def solve(pins,screen_len):
- """
- pin on left or right does not matter since
- there are no overlaps for the pins on each side of column, we do not need to separate it
- """
- # Sort pins by bottom index in ascending order
- pins = sorted(pins, key=lambda p: p[1])
- # Bottom of the sliding window
- window_bot = screen_len
- # The most we need to check is max(screen_len, max of the last pin bot)
- max_bot = max(screen_len, max([p[1] for p in pins]))
- fitted_pins, max_pins = [], 0
- while window_bot <= max_bot:
- window_top = window_bot - screen_len
- # Remove all fitted pins that have now exited the current window, realistically this should only run at most 2 times since
- # we are sliding the window 1 frame at a time and there are 2 columns
- while fitted_pins and (fitted_pins[0][0] < window_top or fitted_pins[0][1] > window_bot):
- fitted_pins.pop(0)
- # Add all pins that fit the current window, again realistically this should only run at most 2 times, 1 for each column
- while pins and (pins[0][0] >= window_top and pins[0][1] <= window_bot):
- fitted_pins.append(pins.pop(0))
- max_pins = max(max_pins, len(fitted_pins))
- window_bot += 1
- return max_pins
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement