All problems

Garden Sprinkler Overlaps

Medium · prefix sum

A long vegetable garden has n beds in a single row, numbered from 1 to n. The gardener has set up several sprinklers. Sprinkler i waters every bed from lefts[i] to rights[i], both included.

A bed is well watered when at least k different sprinklers reach it. A bed that no sprinkler reaches has zero sprinklers on it.

Return the number of well-watered beds.

Examples

Example 1

Input: n = 6, lefts = [1, 2, 4], rights = [3, 5, 6], k = 2

Output: 4

Beds 1 and 6 are reached by one sprinkler each. Beds 2, 3, 4 and 5 are each reached by two.

Example 2

Input: n = 5, lefts = [1], rights = [5], k = 2

Output: 0

Only one sprinkler exists, so no bed can have two.

Example 3

Input: n = 4, lefts = [2], rights = [3], k = 1

Output: 2

Constraints

• 1 <= n <= 10^5
• 1 <= len(lefts) <= 10^5
• len(rights) == len(lefts)
• 1 <= lefts[i] <= rights[i] <= n
• 1 <= k <= 10^5