# Line sweep Technique / 2251. Number of Flowers in Full Bloom

## Problem Statement

\


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

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2022/03/02/ex1new.jpg)

<pre><code><strong>Input: flowers = [[1,6],[3,7],[9,12],[4,13]], poeple = [2,3,7,11]
</strong><strong>Output: [1,2,2,2]
</strong><strong>Explanation: The figure above shows the times when the flowers are in full bloom and when the people arrive.
</strong>For each person, we return the number of flowers in full bloom during their arrival.
</code></pre>

**Example 2:**

![](https://assets.leetcode.com/uploads/2022/03/02/ex2new.jpg)

<pre><code><strong>Input: flowers = [[1,10],[3,3]], poeple = [3,3,2]
</strong><strong>Output: [2,2,1]
</strong><strong>Explanation: The figure above shows the times when the flowers are in full bloom and when the people arrive.
</strong>For each person, we return the number of flowers in full bloom during their arrival.
</code></pre>

&#x20;

**Constraints:**

* `1 <= flowers.length <= 5 * 104`
* `flowers[i].length == 2`
* `1 <= starti <= endi <= 109`
* `1 <= people.length <= 5 * 104`
* `1 <= people[i] <= 109`

## Intuition

```
Line sweep -> sorting + heap


Approach:

Interval type of problem, use sorting and hence prioirity queue for sorting people 

At each juncture we maintain, how much flowers using the count, We check at start 
heap if current time (people) is less than, than flower is bloomed count++

Hence check in end heap to do count--
```

### Links

[https://leetcode.com/problems/number-of-flowers-in-full-bloom/description/](https://leetcode.com/problems/number-of-flowers-in-full-bloom/description/)

### Video Links

[https://www.youtube.com/watch?v=zY3Uty9IwvY\&ab\_channel=NeetCodeIO](https://www.youtube.com/watch?v=zY3Uty9IwvY\&ab_channel=NeetCodeIO)

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}
```cpp
typedef pair<int,int> pii;

class Solution {
public:
    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& people) {
        vector<int> ans(people.size(),0);
        priority_queue<int, vector<int>, greater<int>> start,end;
        vector<pii> pl;

        for(int i=0; i<people.size(); i++)
            pl.push_back({people[i], i});
        
        sort(pl.begin(), pl.end());

        for(auto &it: flowers){
            start.push(it[0]);
            end.push(it[1]);
        }

        int count = 0;

        for(auto &it: pl){
            int time = it.first;
            int idx = it.second;
            while(!start.empty() and start.top() <= time){
                count ++;
                start.pop();
            }
            while(!end.empty() and end.top() < time){
                count--;
                end.pop();
            }

            ans[idx] = count;
        }

        return ans;
    }
};
```
{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}
```cpp
```
{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}
```cpp
```
{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}
```cpp
```
{% endcode %}

### Similar Problems

###

