Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Dynamic programming, O(benches²) solution in Clear category for Park Benches by Rcp8jzd
def park_benches(benches: list[tuple[int, int]], distance: int) -> int:
"""
Remove some benches in order to keep the social distance.
:param benches: A list of the bench's detail (a tuple of the leftmost
coordinate and the length).
:param distance: The minimum social distance between benches.
:return: Maximum total length of the remaining benches.
"""
# A dictionary with key = position of the last bench,
# value = total bench length
best_bench = {}
for (bench_start, length) in benches:
# Get the maximum cumulated bench distance from previous benches
# that comply with the social distance,
# or 0 if no previous bench complies with the social distance.
max_previous = max((v for k, v in best_bench.items()
if k <= bench_start - distance), default=0)
best_bench[bench_start + length] = length + max_previous
return max(best_bench.values())
Jan. 29, 2021
Comments:
