3661. Maximum Walls Destroyed by Robots Hard

1/**
2 * [3661] Maximum Walls Destroyed by Robots
3 *
4 * <div data-docx-has-block-data="false" data-lark-html-role="root" data-page-id="Rax8d6clvoFeVtx7bzXcvkVynwf">
5 * <div class="old-record-id-Y5dGdSKIMoNTttxGhHLccrpEnaf">There is an endless straight line populated with some robots and walls. You are given integer arrays robots, distance, and walls:</div>
6 * </div>
7 * 
8 * 	robots[i] is the position of the i^th robot.
9 * 	distance[i] is the maximum distance the i^th robot's bullet can travel.
10 * 	walls[j] is the position of the j^th wall.
11 * 
12 * Every robot has one bullet that can either fire to the left or the right at most distance[i] meters.
13 * 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.
14 * Return the maximum number of unique walls that can be destroyed by the robots.
15 * Notes:
16 * 
17 * 	A wall and a robot may share the same position; the wall can be destroyed by the robot at that position.
18 * 	Robots are not destroyed by bullets.
19 * 
20 *  
21 * <strong class="example">Example 1:
22 * <div class="example-block">
23 * Input: <span class="example-io">robots = [4], distance = [3], walls = [1,10]</span>
24 * Output: <span class="example-io">1</span>
25 * Explanation:
26 * 
27 * 	robots[0] = 4 fires left with distance[0] = 3, covering [1, 4] and destroys walls[0] = 1.
28 * 	Thus, the answer is 1.
29 * </div>
30 * <strong class="example">Example 2:
31 * <div class="example-block">
32 * Input: <span class="example-io">robots = [10,2], distance = [5,1], walls = [5,2,7]</span>
33 * Output: <span class="example-io">3</span>
34 * Explanation:
35 * 
36 * 	robots[0] = 10 fires left with distance[0] = 5, covering [5, 10] and destroys walls[0] = 5 and walls[2] = 7.
37 * 	robots[1] = 2 fires left with distance[1] = 1, covering [1, 2] and destroys walls[1] = 2.
38 * 	Thus, the answer is 3.
39 * </div>
40 * <strong class="example">Example 3:
41 * <div class="example-block">
42 * Input: <span class="example-io">robots = [1,2], distance = [100,1], walls = [10]</span>
43 * Output: <span class="example-io">0</span>
44 * Explanation:
45 * In this example, only robots[0] can reach the wall, but its shot to the right is blocked by robots[1]; thus the answer is 0.
46 * </div>
47 *  
48 * Constraints:
49 * 
50 * 	1 <= robots.length == distance.length <= 10^5
51 * 	1 <= walls.length <= 10^5
52 * 	1 <= robots[i], walls[j] <= 10^9
53 * 	1 <= distance[i] <= 10^5
54 * 	All values in robots are unique
55 * 	All values in walls are unique
56 * 
57 */
58pub struct Solution {}
59
60// problem: https://leetcode.com/problems/maximum-walls-destroyed-by-robots/
61// discuss: https://leetcode.com/problems/maximum-walls-destroyed-by-robots/discuss/?currentPage=1&orderBy=most_votes&query=
62
63// submission codes start here
64
65impl Solution {
66    pub fn max_walls(robots: Vec<i32>, distance: Vec<i32>, walls: Vec<i32>) -> i32 {
67        0
68    }
69}
70
71// submission codes end
72
73#[cfg(test)]
74mod tests {
75    use super::*;
76
77    #[test]
78    fn test_3661() {
79    }
80}
81