#3661

Maximum Walls Destroyed by Robots

hard · 26.4% accepted · 53 likes · top 4%

array · binary search · dynamic programming · sorting

Description

There is an endless straight line populated with some robots and walls. You are given integer arrays robots, distance, and walls:

- robots[i] is the position of the ith robot.

- distance[i] is the maximum distance the ith robot's bullet can travel.

- walls[j] is the position of the jth wall.

Every robot has one bullet that can either fire to the left or the right at most distance[i] meters.

A bullet destroys every wall in its path that lies within its range. Robots are fixed obstacles: if a bullet hits another robot before reaching a wall, it immediately stops at that robot and cannot continue.

Return the maximum number of unique walls that can be destroyed by the robots.

Notes:

- A wall and a robot may share the same position; the wall can be destroyed by the robot at that position.

- Robots are not destroyed by bullets.

Solution