Flowers in Bloom on Visit Day

Hard

A botanical garden has several plants. The array blooms describes when they flower: blooms[i] = [start, end] means plant i is in bloom from day start through day end, inclusive. The array visits lists when visitors come: visits[j] is the day visitor j arrives. Return an array of the same length as visits whose j-th element is the number of plants in bloom on the day visitor j arrives.

Example 1

blooms=[[2, 5], [4, 8], [10, 10]], visits=[4, 9, 10, 1] → [2, 0, 1, 0]

On day 4 the first two plants are in bloom. On day 9 nothing is: the second finished on day 8 and the third has not opened yet. On day 10 only the third blooms, and on day 1 none do.

Example 2

blooms=[[1, 3], [3, 3]], visits=[3, 3] → [2, 2]

Both ends are inclusive: on day 3 both plants are in bloom, so each visitor sees two.

Constraints

1 ≤ len(blooms) ≤ 5·10⁴
len(blooms[i]) == 2
1 ≤ start ≤ end ≤ 10⁹
1 ≤ len(visits) ≤ 5·10⁴
1 ≤ visits[j] ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Binary Search Ordered Set Prefix Sum Sorting

Similar problems

Climbing Along Rows and Columns Hard Richest Plot Under the Cap Hard Nearest Roomy Enough Room Hard Crates From a Single Supplier Hard Flowerbed Beauty on a Budget Hard

Input

blooms=[[2, 5], [4, 8], [10, 10]], visits=[4, 9, 10, 1]

Expected

[2, 0, 1, 0]

Run checks the first 3 tests in your browser. Submit checks all 102 tests on the server, hidden ones included.