<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 {
public:
    
    
    int binarySearch(vector<pair<int, int>>& flowerCounts, int index) {
        if (index < flowerCounts[0].first) {
            return 0;
        }
        if (index >= flowerCounts[flowerCounts.size() - 1].first){
            return 0;
        }
        int left = 0;
        int right = flowerCounts.size()-1; // 2
        while (left < right - 1) {
            int mid = (left + right) / 2; // 1
            if (flowerCounts[mid].first == index) {
                return flowerCounts[mid].second;
            } else if (flowerCounts[mid].first < index) {
                // we're looking for something bigger
                left = mid;
            } else {
                // we're looking for somthing smaller
                right = mid;
            }
        }
        return flowerCounts[left].second;
    }
    
    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& people) {
        // process the flowers first
        vector<pair<int, int>> events;
        for (int i = 0; i < flowers.size(); i++) {
            int start = flowers[i][0];
            int end = flowers[i][1] + 1;
            events.push_back(make_pair(start, 1));
            events.push_back(make_pair(end, -1));
        }
        
        sort(events.begin(), events.end());
        
        int prev = events[0].first;
        int runner = 0;
        vector<pair<int, int>> flowerCounts; // flowerCounts[i] represents a pair saying that anything from HERE to the next is SECOND flowers
        for (int i = 0; i < events.size(); i++) {
            if (events[i].first == prev) {
                runner += events[i].second;    
            } else {
                // we need to add to flowerCounts
                flowerCounts.push_back(make_pair(prev, runner));
                runner += events[i].second;
                prev = events[i].first;
            }
        }
        flowerCounts.push_back(make_pair(prev, runner));
        
        
        // let people see them
        vector<int> seen(people.size(), 0);
    
        // cout << "HEAD" << endl;
        for (int i = 0; i < people.size(); i++) {
            seen[i] = binarySearch(flowerCounts, people[i]);
        }

        
        return seen;
    }
};
90211