<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) {
        vector<int> res(people.size());
        vector<pair<int, int>> events;
        for (const auto& flower : flowers) {
            events.emplace_back(flower[0], -1); 
            events.emplace_back(flower[1] + 1, 1);
        }

        // Sort the events by time; for same time, end (-1) should come before start (1)
        sort(events.begin(), events.end());

        // Sort people by their arrival times and keep track of their original indices
        vector<pair<int, int>> peopleWithIndices;
        for (int i = 0; i < people.size(); ++i) {
            peopleWithIndices.emplace_back(people[i], i);
        }
        sort(peopleWithIndices.begin(), peopleWithIndices.end());

        // Sweep line algorithm to count the number of flowers in bloom
        int bloomCount = 0;
        int eventIndex = 0;
        for (const auto& [arrivalTime, originalIndex] : peopleWithIndices) {
            // Process all events up to the current person's arrival time
            while (eventIndex < events.size() && events[eventIndex].first <= arrivalTime) {
                bloomCount += (events[eventIndex].second == -1) ? 1 : -1;
                ++eventIndex;
            }
            // The number of flowers in bloom at the current person's arrival time
            res[originalIndex] = bloomCount;
        }

        return res;
    }
};

92121