Number of Flowers in Full Bloom LeetCode solution in Python

1
# Runtime: 931 ms (Top 66.6%) | Memory: 45.16 MB (Top 22.2%)
2

3

4
class Solution:
5
    def fullBloomFlowers(
6
        self, flowers: List[List[int]], people: List[int]
7
    ) -> List[int]:
8
        # we ADD flowers in the order in which they start, but we remove them in the order they
9
        # end.  For this reason, we sort the flowers by starting time but put them in a heap,
10
        # in which we remove them by ending time
11
        starts = sorted(
12
            flowers
13
        )  # keep flowers untouched in case array should be constant
14
        blooming = []  # heap of active flowers
15
        answer = [-1] * len(people)  # output array
16
        hours = [
17
            (people[i], i) for i in range(len(people))
18
        ]  # the people, ordered and indexed by their time
19
        hours.sort()
20

21
        i = 0  # going through starts
22
        for hour, person in hours:
23
            # add all flowers that have started
24
            while i < len(starts) and starts[i][0] <= hour:
25
                heappush(blooming, (starts[i][1], starts[i][0]))
26
                i += 1
27
            # now remove all flowers that have ended.  Note that we only care about the absolute smallest,
28
            # and in python minheaps, that is always the first element - even if no other element's order
29
            # is guaranteed
30
            while (
31
                blooming and blooming[0][0] < hour
32
            ):  # as long as the soonest to end blooming flower hasn't already stopped
33
                heappop(blooming)
34
            answer[person] = len(blooming)
35

36
        return answer