You are given a 0-indexed 2D integer array flowers, where flowers[i] = [starti, endi] means the ith flower will be in full bloom from starti to endi (inclusive). You are also given a 0-indexed integer array people of size n, where people[i] is the time that the ith person will arrive to see the flowers.

Return an integer array answer of size n, where answer[i] is the number of flowers that are in full bloom when the ith person arrives.

For example: flowers = [[1,6],[3,7],[9,12],[4,13]], people = [2,3,7,11] Output: [1,2,2,2] Explanation: The first person arrives at time 2, and only flower [1,6] is in bloom. The second person arrives at time 3, and flowers [1,6] and [3,7] are in bloom, and so on.

flowers = [[1,10],[3,3]], people = [3,3,2] Output: [2,2,1] Explanation: The first and second person arrive at time 3, so both flower [1,10] and [3,3] are in bloom.

# Optimal Solution

This problem can be solved efficiently using a combination of sorting and binary search. The key idea is to separate the start and end times of the flowers into two sorted arrays. Then, for each person's arrival time, we can use binary search to find the number of flowers that have started blooming but not yet ended.

**Algorithm:**

1.  **Separate and Sort:** Create two arrays, `starts` and `ends`, containing the start and end times of the flowers, respectively. Sort both arrays in ascending order.
2.  **Binary Search:** For each person's arrival time `p`, perform two binary searches:
    *   Find the number of flowers that have started blooming by time `p` using binary search on the `starts` array.
    *   Find the number of flowers that have ended blooming by time `p - 1` using binary search on the `ends` array.
3.  **Calculate Bloom Count:** The number of flowers in full bloom at time `p` is the difference between the two counts obtained in step 2.
4.  **Store Result:** Store the bloom count in the `answer` array for each person.

```python
from bisect import bisect_right

def fullBloomFlowers(flowers, people):
    starts = sorted([flower[0] for flower in flowers])
    ends = sorted([flower[1] for flower in flowers])
    answer = []
    for person in people:
        start_count = bisect_right(starts, person)
        end_count = bisect_right(ends, person - 1)
        answer.append(start_count - end_count)
    return answer

Example:

flowers = [[1, 6], [3, 7], [9, 12], [4, 13]]
people = [2, 3, 7, 11]
result = fullBloomFlowers(flowers, people)
print(result)  # Output: [1, 2, 2, 2]

Big(O) Run-time Analysis

• Sorting: Sorting the starts and ends arrays takes O(m log m) time, where m is the number of flowers.
• Binary Search: For each person, we perform two binary searches on arrays of size m, which takes O(log m) time each. Since we have n people, this step takes O(n log m) time.
• Overall: The overall time complexity is O(m log m + n log m).

Big(O) Space Usage Analysis

• Starts and Ends Arrays: We create two arrays, starts and ends, each of size m, to store the start and end times of the flowers. This takes O(m) space.
• Answer Array: We create an array of size n to store the answer for each person. This takes O(n) space.
• Overall: The overall space complexity is O(m + n).

Edge Cases

• Empty Flowers Array: If the flowers array is empty, the number of flowers in bloom will always be 0 for each person. The code handles this case correctly because the starts and ends arrays will be empty, and the binary searches will return 0.
• Empty People Array: If the people array is empty, the function should return an empty array. The code handles this case correctly because the loop will not be executed.
• Flowers with Same Start and End Times: If a flower has the same start and end time (e.g., [3, 3]), it will be considered in full bloom only at that specific time. The binary search will handle this case correctly.
• Large Input: If the input arrays are very large, the code may take a long time to execute. However, the time complexity is still O(m log m + n log m), which is efficient for reasonably sized inputs.

Naive Solution

A brute-force approach would be to iterate through each person and then iterate through each flower to check if it's in bloom at that time. This is very inefficient.

Algorithm:

1. Iterate through each person's arrival time.
2. For each person, iterate through each flower.
3. Check if the flower is in full bloom at the person's arrival time (i.e., start <= arrival_time <= end).
4. Count the number of flowers in full bloom.
5. Store the count in the answer array.

def fullBloomFlowers_naive(flowers, people):
    answer = []
    for person in people:
        count = 0
        for flower in flowers:
            if flower[0] <= person <= flower[1]:
                count += 1
        answer.append(count)
    return answer

Example:

flowers = [[1, 6], [3, 7], [9, 12], [4, 13]]
people = [2, 3, 7, 11]
result = fullBloomFlowers_naive(flowers, people)
print(result)  # Output: [1, 2, 2, 2]

Big(O) Run-time Analysis for Naive Solution:

• The outer loop iterates through each person, which takes O(n) time, where n is the number of people.
• The inner loop iterates through each flower, which takes O(m) time, where m is the number of flowers.
• Therefore, the overall time complexity is O(n * m).

Big(O) Space Usage Analysis for Naive Solution:

• The only extra space used is the answer array, which stores the number of flowers in full bloom for each person. This takes O(n) space.
• Therefore, the overall space complexity is O(n).