<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:
    bool static cmp2(vector<int> &v1,vector<int> &v2){
        return v1[1]<v2[1]; //sort based on original index;
    }
    bool static cmp1(vector<int> &v1,vector<int> &v2){
        return v1[0]<v2[0]; //sort based on people[i] (position);
    }
    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& people) {
        vector<vector<int>> v; //people[i] (position), i (original index), ans (answer for that index);
        for(int i=0;i<people.size();i++){
            v.push_back({people[i],i,0});
        }
        sort(v.begin(),v.end(),cmp1); //based on people[i];
        vector<int> temp; for(int i=0;i<v.size();i++)temp.push_back(v[i][0]); 
        
        for(int i=0;i<flowers.size();i++){
            int left=flowers[i][0]; int right=flowers[i][1];
            int low=lower_bound(temp.begin(),temp.end(),left)-temp.begin();
            int high=upper_bound(temp.begin(),temp.end(),right)-temp.begin(); high--;
            if(low>=0&&low<v.size()) //low should exist in range [0...v.size()-1]
                v[low][2]+=1;
            if(high+1<v.size())      //high should exist in range [0...v.size()-1]
                v[high+1][2]-=1;
        }
        for(int i=1;i<v.size();i++){
            v[i][2]+=v[i-1][2];
        }
        sort(v.begin(),v.end(),cmp2);
        vector<int> answer;
        for(int i=0;i<v.size();i++){
            answer.push_back(v[i][2]);
        }
        return answer;
    }
};
105013