<p>You are given a <strong>0-indexed</strong> 2D integer array <code>flowers</code>, where <code>flowers[i] = [start<sub>i</sub>, end<sub>i</sub>]</code> means the <code>i<sup>th</sup></code> flower will be in <strong>full bloom</strong> from <code>start<sub>i</sub></code> to <code>end<sub>i</sub></code> (<strong>inclusive</strong>). You are also given a <strong>0-indexed</strong> integer array <code>people</code> of size <code>n</code>, where <code>people[i]</code> is the time that the <code>i<sup>th</sup></code> person will arrive to see the flowers.</p>

<p>Return <em>an integer array </em><code>answer</code><em> of size </em><code>n</code><em>, where </em><code>answer[i]</code><em> is the <strong>number</strong> of flowers that are in full bloom when the </em><code>i<sup>th</sup></code><em> person arrives.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/03/02/ex1new.jpg" style="width: 550px; height: 216px;" />
<pre>
<strong>Input:</strong> flowers = [[1,6],[3,7],[9,12],[4,13]], people = [2,3,7,11]
<strong>Output:</strong> [1,2,2,2]
<strong>Explanation: </strong>The figure above shows the times when the flowers are in full bloom and when the people arrive.
For each person, we return the number of flowers in full bloom during their arrival.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/03/02/ex2new.jpg" style="width: 450px; height: 195px;" />
<pre>
<strong>Input:</strong> flowers = [[1,10],[3,3]], people = [3,3,2]
<strong>Output:</strong> [2,2,1]
<strong>Explanation:</strong> The figure above shows the times when the flowers are in full bloom and when the people arrive.
For each person, we return the number of flowers in full bloom during their arrival.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= flowers.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>flowers[i].length == 2</code></li>
	<li><code>1 &lt;= start<sub>i</sub> &lt;= end<sub>i</sub> &lt;= 10<sup>9</sup></code></li>
	<li><code>1 &lt;= people.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= people[i] &lt;= 10<sup>9</sup></code></li>
</ul>

import numpy as np

class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
        people_arrival_order = np.argsort(people)
        event_times = defaultdict(int)
        event_heap = []

        for start, end in flowers:
            event_times[start] += 1
            event_times[end + 1] -= 1

        for time, delta in event_times.items():
            heappush(event_heap, (time, delta))
        
        num_in_bloom = 0
        person_index = 0
        blooms_seen = [0] * len(people)

        while event_heap:
            cur_time, delta = heappop(event_heap)
            print(cur_time, delta)

            while person_index < len(people) and people[people_arrival_order[person_index]] <= cur_time:
                if people[people_arrival_order[person_index]] == cur_time:
                    blooms_seen[people_arrival_order[person_index]] += delta
                
                blooms_seen[people_arrival_order[person_index]] += num_in_bloom
                person_index += 1
    
            num_in_bloom += delta

        for i in range(person_index, len(people)):
            blooms_seen[people_arrival_order[person_index]] = 0

        return blooms_seen
            


        
        # Idea 1: Running sum for bloom, preprocess start/end event times
        # [[0,3], [3, 5], [6,7]]
        # bloom_counter (+1 for start, -1 for end): [0,0,0,0,0,0,0]
        # After preproc: [1,0,0,-1 + 1 = 0, 0,-1, 1, -1]
        # Running sum: 1,1,1,1,1,0,1,0
        # People need to be sorted by the time they arrive (use argsort)

        # Runtime: argsort people arriving + iterate through all start/end events + sort start/end events
        # Runtime: O(nlogn + f + flogf) = O(nlogn + flogf)
        # Space: store events = O(f)
1159