<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>

'''
This is like Meeting Rooms II, so Priority Queue
'''
import heapq
class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
        n = len(people)
        answer = [0] * n
        numFlowers = 0
        minHeap = []    # keep a tuple of (time, event type, idx)

        # Okay, so heap will sort by time, then it will check the 2nd element, so we need to make sure
        # we get the start, then the person, and lastly check the end. 
        # As such, for event type: start = -1, person = 0, end = 1
        for start, end in flowers:
            minHeap.append((start, -1, -1))  # (START, -1 to have it first, -1 to ensure before people)
            minHeap.append((end, 1, -1))   # (END, 1 to have it last, -1 to ensure before people)
        
        for i, arrivalTime in enumerate(people):
            minHeap.append((arrivalTime, 0, i)) # (ARRIVAL TIME, 0 to indicate person creeping, idx)

        heapify(minHeap)

        while minHeap:
            time, eventType, idx = heappop(minHeap)
            
            # Add a flower as this indicates the start of full bloom
            if eventType == -1:
                numFlowers += 1
            # Cool person arrived, watch out
            elif eventType == 0:
                answer[idx] = numFlowers
            # End of bloom
            else:
                numFlowers -= 1
        return answer
        
1011