---
# System prepended metadata

title: 2251. Number of Flowers in Full Bloom
tags: [Leetcode, Line Sweep, Hard]

---

# 2251. Number of Flowers in Full Bloom
###### tags: `Leetcode` `Hard` `Line Sweep`
Link: https://leetcode.com/problems/number-of-flowers-in-full-bloom/
## 思路
依然是line sweep的题
但是由于start和end的最大值会到$10^9$, 超出memory size了 所以改用TreeMep
## Code
```java=
class Solution {
    public int[] fullBloomFlowers(int[][] flowers, int[] persons) {
        TreeMap<Integer, Integer> blooms = new TreeMap<>();
        for(int[] flower:flowers){
            blooms.put(flower[0], blooms.getOrDefault(flower[0], 0)+1);
            blooms.put(flower[1]+1, blooms.getOrDefault(flower[1]+1, 0)-1);
        }
        
        int prev = 0;
        TreeMap<Integer, Integer> sum = new TreeMap<>();
        for(Map.Entry<Integer, Integer> entry:blooms.entrySet()){
            prev += entry.getValue();
            sum.put(entry.getKey(), prev);
        }
        
        int[] ans = new int[persons.length];
        for(int i=0; i<persons.length; i++){
            int person = persons[i];
            Map.Entry<Integer, Integer> entry = sum.floorEntry(person);
            if(entry!=null) ans[i] = entry.getValue();
        }
        
        return ans;
    }
}
```