<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:
    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& people) {
        
        // array of pairs (intervals)
        vector<int> answer(people.size(), 0);

        //  vector of max(end) size
        //  O(1) access
        // way too long to increment all of the intervals

        // naive O(flowers * n) + O(people)

        // 
        // 
        // an idea:
        // naive: for each person, check  FOR EACH FLOWER, if greater and less than beg/end
        // O(people*flower)
        
        // optimization: sort each person. sort flowers (by beginning)
        // now, only a subset of flower-ranges is discovered for each person - know when to stop looking for flower-ranges

        // need to retain their indices
        vector<pair<int, int>> pt; // idx, time
        for (int i = 0; i < people.size(); i++) {
            pt.push_back({i, people[i]});
        }

        // sort peioke
        std::sort(pt.begin(), pt.end(), pairsecondLess{});
        // sort flower-ranges also by time
        vector<pair<int, int>> fb;
        for (auto f : flowers) {
            fb.push_back({f[0],f[1]});
        }
        sort(fb.begin(), fb.end(), pairfirstLess{}); // beginnings, asc
        vector<pair<int, int>> fe;
        fe = fb;
        sort(fe.begin(), fe.end(), pairsecondLess{}); // ends, asc

        // so far: O(3nlogn)

        // iterate over people
        int bi = 0;
        int ei = 0;
        int count = 0;
        for (int i = 0; i < pt.size(); i++) {
            int time = pt[i].second;
            // while start time <= people time
            while (bi < fb.size() && fb[bi].first <= time) {
                bi += 1;
                count += 1;
            }
            // bi -= 1; // for if people are the same
            // have encountered first start time that exceeds the guy
            // do the same for 
            // while end times < people time (counting erasures)
            while (ei < fe.size() && fe[ei].second < time) {
                ei += 1;
                count -= 1;
            }
            answer[pt[i].first] = count;
        }
        return answer;

    }
    struct pairsecondLess {
        bool operator()(std::pair<int, int>& p1, std::pair<int, int>& p2) {
            return p1.second < p2.second; // sorts by TIME, ascending
        }
    };
    struct pairfirstLess {
        bool operator()(std::pair<int, int>& p1, std::pair<int, int>& p2) {
            return p1.first < p2.first; // sorts by TIME, ascending
        }
    };

};
96896