Solution Explanation: Number of Flowers in Full Bloom

This problem asks to find the number of flowers in full bloom for each person's arrival time. The most efficient solutions leverage sorting and binary search or a difference array for optimal time complexity. Let's explore both approaches.

Approach 1: Sorting + Binary Search

1. Data Preparation:

   • Create two sorted arrays: start_times and end_times. start_times contains the start times of all flowers, sorted in ascending order. end_times contains the end times of all flowers, also sorted in ascending order.

2. Querying for Each Person:

   • For each person's arrival time p:
     • Use binary search on start_times to find the index r such that start_times[r] <= p. This represents the number of flowers that have started blooming by time p.
     • Use binary search on end_times to find the index l such that end_times[l] < p. This represents the number of flowers that have already wilted by time p.
     • The number of flowers in bloom at time p is r - l.

Time Complexity Analysis:

• Sorting start_times and end_times: O(m log m), where m is the number of flowers.
• Binary search for each person: O(n log m), where n is the number of people.
• Total Time Complexity: O((m + n) log m)

Space Complexity Analysis:

• start_times and end_times arrays: O(m) space.
• Total Space Complexity: O(m)

Approach 2: Difference Array + Sorting + Offline Query

1. Difference Array:

   • Create a difference array diff (a map or dictionary) to store the changes in the number of blooming flowers at each time point.
   • For each flower [start, end], increment diff[start] by 1 (a new flower blooms) and decrement diff[end + 1] by 1 (the flower wilts).

2. Sorting and Offline Query:

   • Sort the people array by arrival time.
   • Iterate through the sorted people array. For each person:
     • Iterate through the diff array (sorted by keys) until the current time exceeds the person's arrival time.
     • Accumulate the values in diff (representing the total number of blooming flowers) until you reach the person's arrival time. This gives you the number of flowers in bloom for that person.

Time Complexity Analysis:

• Creating the difference array: O(m)
• Sorting people: O(n log n)
• Iterating through sorted people and diff: O(m + n) in the best case (assuming mostly unique arrival times and flower bloom durations), potentially O(m*n) in the worst case if many overlaps occur
• Total Time Complexity: O(m + n log n) or O(m*n)

Space Complexity Analysis:

• diff array: O(m)
• Sorted people: O(n)
• Total Space Complexity: O(m + n)

Code Examples (Python):

Approach 1 (Sorting + Binary Search):

import bisect
 
def fullBloomFlowers(flowers, people):
    start_times = sorted([start for start, _ in flowers])
    end_times = sorted([end for _, end in flowers])
    result = []
    for person_time in people:
        blooming_flowers = bisect.bisect_right(start_times, person_time) - bisect.bisect_left(end_times, person_time)
        result.append(blooming_flowers)
    return result
 

Approach 2 (Difference Array):

from collections import defaultdict
 
def fullBloomFlowers(flowers, people):
    diff = defaultdict(int)
    for start, end in flowers:
        diff[start] += 1
        diff[end + 1] -= 1
 
    sorted_times = sorted(diff.keys())
    sorted_people_with_indices = sorted(enumerate(people), key=lambda x: x[1])
    
    result = [0] * len(people)
    blooming_count = 0
    time_index = 0
 
    for person_index, person_time in sorted_people_with_indices:
        while time_index < len(sorted_times) and sorted_times[time_index] <= person_time:
            blooming_count += diff[sorted_times[time_index]]
            time_index += 1
        result[person_index] = blooming_count
    return result
 

The choice between these approaches depends on the expected distribution of input data. If m (number of flowers) is significantly larger than n (number of people), Approach 1 might be slightly faster. If n is larger or comparable to m, and the distribution of flower bloom times and arrival times is relatively spread out, Approach 2 could be faster. If there are many overlaps, Approach 2 could be slower. However, Approach 2 generally uses less space. Consider the constraints and expected inputs when selecting an approach.