We’re given a list of flowers with format [(start_i, end_i) … (start_n, end_n)], and a list of people where people[i] is the time when a person will be present. We’re asked to return a list correlating with people that determines the number of flowers that will be in full bloom when person[i] is present.
The most intuitive way to solve this is to pre-process the input flowers list, creating a list of start and end times, sorted in ascending order. For each person, we’ll maintain two pointers for the start and end times, i and j. i will describe the number of flowers that bloom before or during a person’s visit. j will describe the number of flowers that stop blooming before the person’s visit. We find i and j by binary searching through the start and end times with the time person[i] appears.
Taking the difference of i and j, we can determine the number of flowers in full bloom when person[i] is present. We repeat this process for each person and return the list of flowers in full bloom.
The solution is as follows:
from bisect import bisect_right
class Solution:
def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
starts = sorted([start for start, _ in flowers])
ends = sorted([end + 1 for _, end in flowers])
m, n = len(flowers), len(people)
ans = []
for k in range(n):
i = bisect_right(starts, people[k])
j = bisect_right(ends, people[k])
ans.append(i - j)
return ans_ Time Complexity:
O((m + n) log(m)) - We preprocess m flowers and iterate through n people, executing binary search on m flowers for each person.
_ Space Complexity:
O(m) - We store two arrays of m flower starts and ends.