Welcome to Subscribe On Youtube
2237. Count Positions on Street With Required Brightness
Description
You are given an integer n
. A perfectly straight street is represented by a number line ranging from 0
to n  1
. You are given a 2D integer array lights
representing the street lamp(s) on the street. Each lights[i] = [position_{i}, range_{i}]
indicates that there is a street lamp at position position_{i}
that lights up the area from [max(0, position_{i}  range_{i}), min(n  1, position_{i} + range_{i})]
(inclusive).
The brightness of a position p
is defined as the number of street lamps that light up the position p
. You are given a 0indexed integer array requirement
of size n
where requirement[i]
is the minimum brightness of the i^{th}
position on the street.
Return the number of positions i
on the street between 0
and n  1
that have a brightness of at least requirement[i]
.
Example 1:
Input: n = 5, lights = [[0,1],[2,1],[3,2]], requirement = [0,2,1,4,1] Output: 4 Explanation:  The first street lamp lights up the area from [max(0, 0  1), min(n  1, 0 + 1)] = [0, 1] (inclusive).  The second street lamp lights up the area from [max(0, 2  1), min(n  1, 2 + 1)] = [1, 3] (inclusive).  The third street lamp lights up the area from [max(0, 3  2), min(n  1, 3 + 2)] = [1, 4] (inclusive).  Position 0 is covered by the first street lamp. It is covered by 1 street lamp which is greater than requirement[0].  Position 1 is covered by the first, second, and third street lamps. It is covered by 3 street lamps which is greater than requirement[1].  Position 2 is covered by the second and third street lamps. It is covered by 2 street lamps which is greater than requirement[2].  Position 3 is covered by the second and third street lamps. It is covered by 2 street lamps which is less than requirement[3].  Position 4 is covered by the third street lamp. It is covered by 1 street lamp which is equal to requirement[4]. Positions 0, 1, 2, and 4 meet the requirement so we return 4.
Example 2:
Input: n = 1, lights = [[0,1]], requirement = [2] Output: 0 Explanation:  The first street lamp lights up the area from [max(0, 0  1), min(n  1, 0 + 1)] = [0, 0] (inclusive).  Position 0 is covered by the first street lamp. It is covered by 1 street lamp which is less than requirement[0].  We return 0 because no position meets their brightness requirement.
Constraints:
1 <= n <= 10^{5}
1 <= lights.length <= 10^{5}
0 <= position_{i} < n
0 <= range_{i} <= 10^{5}
requirement.length == n
0 <= requirement[i] <= 10^{5}
Solutions

class Solution { public int meetRequirement(int n, int[][] lights, int[] requirement) { int[] d = new int[100010]; for (int[] e : lights) { int i = Math.max(0, e[0]  e[1]); int j = Math.min(n  1, e[0] + e[1]); ++d[i]; d[j + 1]; } int s = 0; int ans = 0; for (int i = 0; i < n; ++i) { s += d[i]; if (s >= requirement[i]) { ++ans; } } return ans; } }

class Solution { public: int meetRequirement(int n, vector<vector<int>>& lights, vector<int>& requirement) { vector<int> d(100010); for (auto& e : lights) { int i = max(0, e[0]  e[1]), j = min(n  1, e[0] + e[1]); ++d[i]; d[j + 1]; } int s = 0, ans = 0; for (int i = 0; i < n; ++i) { s += d[i]; if (s >= requirement[i]) ++ans; } return ans; } };

class Solution: def meetRequirement( self, n: int, lights: List[List[int]], requirement: List[int] ) > int: d = [0] * 100010 for p, r in lights: i, j = max(0, p  r), min(n  1, p + r) d[i] += 1 d[j + 1] = 1 return sum(s >= r for s, r in zip(accumulate(d), requirement))

func meetRequirement(n int, lights [][]int, requirement []int) int { d := make([]int, 100010) for _, e := range lights { i, j := max(0, e[0]e[1]), min(n1, e[0]+e[1]) d[i]++ d[j+1] } var s, ans int for i, r := range requirement { s += d[i] if s >= r { ans++ } } return ans }