<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]:
        """
        The question is an interval question
        You are given start and end times for when a flower is in full bloom
        You are given a people array which tells you what time they show up
        For that time, how many flowers will be in full bloom?
        Interval is inclusive

        Edge cases:
        What if there are no flowers? No people?
        Data type of input
        Maximum size of flowers array? People array?
        Can an interval start and end at same time?

        Very brute force:
        For every person, check if the value is in between the intervals
        O(n*m) where n is size of people array and m is size of flowers array

        How to optimize?
        Precompute how many flowers at every time interval?
        Would take a lot of memory and time in worst case

        If the # of flowers in bloom is how many started - how many ended
        Add all intervals to two heaps
        While the top of the heaps have intervals that are <= current person
        tally

        Keep two arrays of start and end intervals, sorted
        Binary search current person to find which index it should be
        inserted into
        index of start - index of end = flowers in bloom
        """

        def binarySearch(arr, value, inclusive):
            l, r = 0, len(arr)-1

            while l <= r:
                m = l + (r-l)//2

                if arr[m] <= value if inclusive else arr[m] < value:
                    l = m+1
                else:
                    r = m-1
            return l

        starts, ends = [], []
        for start, end in flowers:
            starts.append(start)
            ends.append(end)
        starts.sort()
        ends.sort()

        ans = []
        for person in people:
            ans.append(binarySearch(starts, person, True) - binarySearch(ends, person, False))
        return ans

        # startHeap, endHeap = [], []
        # for start, end in flowers:
        #     heappush(startHeap, start)
        #     heappush(endHeap, end)
        
        
        # ans = []
        # count = 0
        # people.sort()
        # for person in people:
        #     while startHeap and startHeap[0] <= person:
        #         heappop(startHeap)
        #         count += 1
        #     while endHeap and endHeap[0] < person:
        #         heappop(endHeap)
        #         count -= 1
        #     ans.append(count)
        # return ans

        # ans = []
        # for person in people:
        #     count = 0
        #     for start, end in flowers:
        #         if start <= person <= end:
        #             count += 1
        #     ans.append(count)
        # return ans
1172