1018. Flowers in Bloom
A botanical garden records, for every flower, a closed interval flowers[i] = [start, end]: the flower is open at every integer time t with start <= t <= end. Visitors arrive at the integer times listed in people, and several visitors may arrive at the same time.
Return an array answer of the same length as people where answer[j] is the number of flowers open at time people[j]. The order of answer follows the order of people; the input arrays are not necessarily sorted.
Example 1
- Input:
- flowers = [[1,4],[3,6],[5,8]], people = [2,4,6,9]
- Output:
- [1,2,2,0]
- Explanation:
At time 2 only the first flower is open; at 4 the first two; at 6 the last two; at 9 none (bloom intervals include both endpoints).
Example 2
- Input:
- flowers = [[2,2],[2,2]], people = [2,1,3]
- Output:
- [2,0,0]
- Explanation:
Both flowers are open only at time 2, and neither is open at 1 or 3.
Example 3
- Input:
- flowers = [[1,10]], people = [5]
- Output:
- [1]
- Explanation:
The single flower covers time 5.
Constraints
- 1 ≤ flowers.length ≤ 5 * 104
- 1 ≤ people.length ≤ 5 * 104
- 1 ≤ start ≤ end ≤ 109
- 1 ≤ people[j] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O((F + P) log F)
- Space
- O(F + P)