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

class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
        # sort_people = sorted(people)
        # dic = dict()
        # flowers.sort(reverse = True)
        # heap = [] #min heap
        # for p in sort_people:
        #     while flowers and flowers[-1][0] <= p:
        #         flower = flowers.pop()
        #         heapq.heappush(heap, flower[1])
        #     while heap and heap[0] < p:
        #         heapq.heappop(heap)
        #     dic[p] = len(heap)
        # return [dic[p] for p in people]

        #min idx that is not possible
        def binary_search(target, arr):
            lo, hi = 0, len(start)
            while lo<hi:
                mid = (lo+hi)//2
                if arr[mid] <= target: # possible condition
                    lo = mid + 1
                else:
                    hi = mid 
            return lo 

        def binary_end(target):
            lo, hi = 0, len(end)
            while lo<hi:
                mid = (lo+hi)//2
                if end[mid] < target:
                    lo = mid+1
                else:
                    hi = mid
            return lo # min possible idx

        start, end = [], []
        for s, e in flowers:
            start.append(s)
            end.append(e)
        start.sort()
        end.sort()
        ans = []
        for t in people:
            s = binary_search(t, start)
            # e = binary_search(t, end)
            # s = binary_start(t)
            e = binary_end(t)
            # number of flowers that have already started blooming minus the amount of flowers have finished blooming
            ans.append(s-e)
        return ans
        
1079