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

"""
sort flowers by start time
construct an array which has info about (start time, # flowers)
sorted by start time

for each person, binary search this array, we want to find closest
time less than arrival

where n is flowers, m is people
O(nlogn + mlogn)
"""
from dataclasses import dataclass

@dataclass
class FlowerEvent:
    time: int
    start: bool


@dataclass
class FlowerData:
    time: int
    numFlowers: int


class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
        events = [None] * (len(flowers) * 2)
        for i in range(0, len(flowers)):
            events[i * 2] = FlowerEvent(flowers[i][0], True)
            events[i * 2 + 1] = FlowerEvent(flowers[i][1] + 1, False)
        events.sort(key=lambda fe: fe.time)
        data = [None] * len(events)
        curFlowers = 0
        for idx, event in enumerate(events):
            if event.start:
                curFlowers += 1
            else:
                curFlowers -= 1
            data[idx] = FlowerData(event.time, curFlowers)

        answer = [0] * len(people)
        for idx, time in enumerate(people):
            flowers = 0
            l, r = 0, len(data) - 1
            while l <= r:
                m = (l + r) // 2
                if data[m].time <= time:
                    flowers = data[m].numFlowers
                    l = m + 1
                else:
                    r = m - 1
            answer[idx] = flowers

        return answer

1190