1128. Exactly K Coverage
A street has lamp posts at integer positions, and several repair crews each tape off a stretch of it. Crew i works on the closed segment between segments[i][0] and segments[i][1], and the two ends may be given in either order. Every integer point between the ends, inclusive, belongs to that segment.
Return how many integer points are covered by exactly k segments. Points covered by fewer or more segments do not count. Mark the start and the end plus one of each segment in a difference array, then take running sums.
Constraints: 1 <= segments.length <= 500, 0 <= a, b <= 1000 for the two ends of a segment and 1 <= k <= 500. The intended solution runs in O(n + V) time with O(V) space, where V = 1001.
Example 1
- Input:
- segments = [[1,5],[3,8],[4,4]], k = 2
- Output:
- 2
- Explanation:
Points 3, 4 and 5 lie under exactly two segments, so the answer is 3.
Example 2
- Input:
- segments = [[10,2],[2,10]], k = 2
- Output:
- 9
- Explanation:
Both segments cover points 2 to 10 (the first is given with its ends swapped), which is 9 points.
Constraints
1 ≤ segments.length ≤ 500
0 ≤ a, b ≤ 1000
1 ≤ k ≤ 500
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n + V)
- Space
- O(V)