Show problems as
Classic problem #2237MediumArrayPrefix Sum

Count Positions on Street With Required Brightness

Real-world version: Posts Meeting Their Light Quota
Tracked in this browser only
Read Count Positions on Street With Required Brightness on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A lane has n posts numbered 0 through n - 1. Each entry lights[j] = [at, reach] is a lamp standing at post at that lights every post from at - reach to at + reach inclusive, clipped to the lane. Several lamps may stand at the same post.

The brightness of a post is how many lamps light it. requirement[i] is the brightness post i must have.

Return how many posts have brightness at least their requirement.

Examples

Example 1

Input
n = 5, lights = [[0, 1], [2, 1], [3, 2]], requirement = [0, 2, 1, 4, 1]
Output
4

The posts end up with brightness 1, 2, 2, 2 and 2. Posts 0, 1, 2 and 4 each reach their requirement, while post 3 needs 4 and has 2.

Example 2

Input
n = 4, lights = [[0, 100000]], requirement = [1, 1, 1, 1]
Output
4

The single lamp reaches far beyond both ends of the lane, so every post is lit once and all four requirements of 1 are met.

Example 3

Input
n = 3, lights = [[1, 0]], requirement = [0, 0, 0]
Output
3

Every post needs no light at all, so all three qualify whatever the lamp reaches.

Constraints

  • 1 <= n <= 10^5
  • 1 <= lights.length <= 10^5
  • lights[j].length == 2
  • 0 <= lights[j][0] <= 99999
  • 0 <= lights[j][1] <= 10^5
  • requirement.length == n
  • 0 <= requirement[i] <= 10^5
  • Every lamp stands at a post inside the lane

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def posts_meeting_quota(n: int, lights: list[list[int]], requirement: list[int]) -> int:
Java
public int postsMeetingQuota(int n, int[][] lights, int[] requirement)

More on the same topics