Lamps along a corridor light closed ranges of integer positions: lamp [a, b] lights every position a <= x <= b. Given lamps and a list of integer queries, return a list where the i-th value is how many lamps light position queries[i].
Examples
Input: lamps = [[1, 4], [3, 6], [8, 8]], queries = [0, 3, 4, 6, 8, 9]
Output: [0, 2, 2, 1, 1, 0]
Explanation: Position 3 is inside [1, 4] and [3, 6]; position 8 is lit only by [8, 8].
Input: lamps = [], queries = [5]
Output: [0]
Constraints
0 <= len(lamps) <= 5 * 10**4,0 <= a <= b <= 10**5.1 <= len(queries) <= 10**3,0 <= queries[i] <= 10**5.- Target complexity: O(n + M + q) where
Mis the largest position.
Goals
- Mark interval boundaries in a difference array instead of filling every point
- Turn the difference array into per-point counts with one prefix pass