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] = [positioni, rangei] indicates that there is a street lamp at position
positioni that lights up the area from [max(0, positioni - rangei), min(n -1, positioni + rangei)] (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 0-indexed integer array
requirement of size n where requirement[i] is the minimum brightness of the ith position on the street.
Return the number of positionsion the street between0andn - 1
_that have abrightness _ofat leastrequirement[i].
Input: n =5, lights =[[0,1],[2,1],[3,2]], requirement =[0,2,1,4,1]Output: 4Explanation:
- 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 0is covered by the first street lamp. It is covered by 1 street lamp which is greater than requirement[0].- Position 1is covered by the first, second, and third street lamps. It is covered by 3 street lamps which is greater than requirement[1].- Position 2is covered by the second and third street lamps. It is covered by 2 street lamps which is greater than requirement[2].- Position 3is covered by the second and third street lamps. It is covered by 2 street lamps which is less than requirement[3].- Position 4is 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 return4.
Example 2:
1
2
3
4
5
6
Input: n =1, lights =[[0,1]], requirement =[2]Output: 0Explanation:
- The first street lamp lights up the area from [max(0,0-1), min(n -1,0+1)]=[0,0](inclusive).- Position 0is covered by the first street lamp. It is covered by 1 street lamp which is less than requirement[0].- We return0 because no position meets their brightness requirement.
To efficiently compute the brightness at each position, we use a difference array to mark the effect of each lamp’s range, then take a prefix sum to get the brightness at each position. This allows us to process all lamps in O(n + m) time.
classSolution {
public:int meetRequirement(int n, vector<vector<int>>& lights, vector<int>& requirement) {
vector<int> diff(n+1, 0);
for (auto& l : lights) {
int lft = max(0, l[0] - l[1]), rgt = min(n-1, l[0] + l[1]);
diff[lft]++;
if (rgt+1< n) diff[rgt+1]--;
}
int ans =0, cur =0;
for (int i =0; i < n; ++i) {
cur += diff[i];
if (cur >= requirement[i]) ans++;
}
return ans;
}
};
classSolution {
publicintmeetRequirement(int n, int[][] lights, int[] requirement) {
int[] diff =newint[n+1];
for (int[] l : lights) {
int lft = Math.max(0, l[0]- l[1]), rgt = Math.min(n-1, l[0]+ l[1]);
diff[lft]++;
if (rgt+1 < n) diff[rgt+1]--;
}
int ans = 0, cur = 0;
for (int i = 0; i < n; i++) {
cur += diff[i];
if (cur >= requirement[i]) ans++;
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
classSolution {
funmeetRequirement(n: Int, lights: Array<IntArray>, requirement: IntArray): Int {
val diff = IntArray(n+1)
for (l in lights) {
val lft = maxOf(0, l[0] - l[1])
val rgt = minOf(n-1, l[0] + l[1])
diff[lft]++if (rgt+1 < n) diff[rgt+1]-- }
var ans = 0; var cur = 0for (i in0 until n) {
cur += diff[i]
if (cur >= requirement[i]) ans++ }
return ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classSolution:
defmeetRequirement(self, n: int, lights: list[list[int]], requirement: list[int]) -> int:
diff = [0] * (n+1)
for pos, rng in lights:
lft = max(0, pos - rng)
rgt = min(n-1, pos + rng)
diff[lft] +=1if rgt+1< n:
diff[rgt+1] -=1 ans = cur =0for i in range(n):
cur += diff[i]
if cur >= requirement[i]:
ans +=1return ans
impl Solution {
pubfnmeet_requirement(n: i32, lights: Vec<Vec<i32>>, requirement: Vec<i32>) -> i32 {
let n = n asusize;
letmut diff =vec![0; n+1];
for l in&lights {
let lft = l[0] - l[1];
let lft =if lft <0 { 0 } else { lft } asusize;
let rgt = l[0] + l[1];
let rgt =if rgt >= n asi32 { n asi32-1 } else { rgt } asusize;
diff[lft] +=1;
if rgt+1< n { diff[rgt+1] -=1; }
}
letmut ans =0;
letmut cur =0;
for i in0..n {
cur += diff[i];
if cur >= requirement[i] { ans +=1; }
}
ans asi32 }
}