Statement▼
You are given a 0-indexed 2D integer array, flowers, where each element flowers[i]
You are also given a 0-indexed integer array, people, of size people[i] denotes the time at which the
For each person, determine how many flowers are in full bloom at their arrival time. Return an integer array, ans, of length ans[i] is the number of blooming flowers when the
Constraints:
1
≤ flowers.length≤ 103 flowers[i].length==2 1
≤ starti ≤ endi ≤ 104 1
≤ people.length≤ 103 1
≤ people[i]≤ 104
Solution
The core intuition behind this solution is to avoid directly simulating flower blooming across all possible time values, which would be inefficient. Instead, we transform the problem into one of counting intervals using binary search. The challenge is to determine a person’s arrival time. The difference between these two counts gives the number of flowers in bloom at that moment.
To achieve this, the solution separates the flowers’ intervals into two lists: one for start times and one for end times. The key trick is that the end times are stored as
Let’s break down the key steps of the solution:
Initialize the
startsandendsarrays for storing start and end times, respectively.Iterate over each flower interval
[starti,endi] .Add
starti to thestartslist.Add
endi+1 to theendslist (to account for inclusive ranges).
Sort both lists to ensure that binary search can efficiently count the number of flowers that started or ended before a given arrival time.
Create an
anslist of sizen to store the answer for each person.Iterate over
peoplearray and for each person’s arrival time, perform two binary searches:On
starts, find how many flowers began blooming at or before the arrival time.On
ends, find how many flowers had already finished blooming before the arrival time.Store the difference between the counts in the
ansarray.
After completing the iteration, return the
ansarray as the output.
Binary search implementation details:
The
binarySearchfunction is a modified version of the standard algorithm.It returns the index of the first element greater than the target (
upper bound).This effectively gives the count of values
≤ target.
Let’s look at the following illustration to get a better understanding of the solution: