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

"""
2251. Number of Flowers in Full Bloom

You are given a 0-indexed 2D integer array flowers, where
flowers[i] = [starti, endi] means the ith flower will be in full bloom from
starti to endi (inclusive). You are also given a 0-indexed integer array
people of size n, where people[i] is the time that the ith person will arrive
to see the flowers.

Return an integer array answer of size n, where answer[i] is the number of
flowers that are in full bloom when the ith person arrives.
"""
from typing import List


class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
        start_times = sorted(start for start, _ in flowers)
        end_times = sorted(end for _, end in flowers)

        flower_count = [0] * len(people)

        for i, person in enumerate(people):
            bloom_count = self.count_less_than_eq(start_times, person)
            dead_count = self.count_less_than(end_times, person)
            flower_count[i] = bloom_count - dead_count

        return flower_count

    def count_less_than_eq(self, arr: List[int], value: int) -> int:
        """returns the number of elements less and equals to the value"""
        index = -1
        left, right = 0, len(arr) - 1

        while left <= right:
            mid = left + (right - left) // 2
            if arr[mid] <= value:
                index = mid
                left = mid + 1
            else:
                right = mid - 1

        return index - 0 + 1

    def count_less_than(self, arr: List[int], value: int) -> int:
        """returns the number of elements less than value"""
        index = -1
        left, right = 0, len(arr) - 1

        while left <= right:
            mid = left + (right - left) // 2
            if arr[mid] < value:
                index = mid
                left = mid + 1
            else:
                right = mid - 1

        return index - 0 + 1

    def naive_solution_fullBloomFlowers(self, flowers: List[List[int]],
                                        people: List[int]) -> List[int]:
        ans = []
        for person in people:
            flower = 0
            for start, end in flowers:
                if person in range(start, end + 1):
                    flower += 1

            ans.append(flower)

        return ans

1122