Maximum Walls Destroyed by Robots
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 thei^throbot.distance[i]is the maximum distance thei^throbot's bullet can travel.walls[j]is the position of thej^thwall.
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.
Example 1
Input
robots = [4], distance = [3], walls = [1,10]Output
1The robot at position 4 fires left with distance 3, covering [1, 4] and destroying the wall at position 1.
Example 2
Input
robots = [10,2], distance = [5,1], walls = [5,2,7]Output
3The robot at position 10 destroys walls at positions 5 and 7 by firing left, and the robot at position 2 destroys the wall at position 2 by firing left.
Constraints
- 1 <= robots.length == distance.length <= 10^5
- 1 <= walls.length <= 10^5
- 1 <= robots[i], walls[j] <= 10^9
- 1 <= distance[i] <= 10^5
- All values in
robotsare unique - All values in
wallsare unique