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 persons of size n, where persons[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.

&nbsp;
Example 1:

Input: flowers = [[1,6],[3,7],[9,12],[4,13]], persons = [2,3,7,11]
Output: [1,2,2,2]
Explanation: 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.


Example 2:

Input: flowers = [[1,10],[3,3]], persons = [3,3,2]
Output: [2,2,1]
Explanation: 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.


&nbsp;
Constraints:


	1 &lt;= flowers.length &lt;= 5 * 104
	flowers[i].length == 2
	1 &lt;= starti &lt;= endi &lt;= 109
	1 &lt;= persons.length &lt;= 5 * 104
	1 &lt;= persons[i] &lt;= 109


class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
        #we ADD flowers in the order in which they start, but we remove them in the order they 
        #end.  For this reason, we sort the flowers by starting time but put them in a heap, 
        #in which we remove them by ending time
        starts = sorted(flowers) #keep flowers untouched in case array should be constant
        blooming = [] #heap of active flowers
        answer = [-1] * len(people) #output array
        hours = [(people[i], i) for i in range(len(people))] #the people, ordered and indexed by their time
        hours.sort()

        i = 0 #going through starts
        for hour, person in hours:
            #add all flowers that have started
            while i < len(starts) and starts[i][0] <= hour:
                heappush(blooming, (starts[i][1], starts[i][0]))
                i += 1
            #now remove all flowers that have ended.  Note that we only care about the absolute smallest, 
            #and in python minheaps, that is always the first element - even if no other element's order 
            #is guaranteed
            while blooming and blooming[0][0] < hour: #as long as the soonest to end blooming flower hasn't already stopped
                heappop(blooming)
            answer[person] = len(blooming)
        
        return answer
class Solution {
public int[] fullBloomFlowers(int[][] flowers, int[] persons) {
        int n = persons.length;
        int[] result = new int[n];

        TreeMap<Integer, Integer> treeMap = new TreeMap<>();
        // See explanation here: https://leetcode.com/problems/my-calendar-iii/discuss/109556/JavaC%2B%2B-Clean-Code
        for (int[] flower : flowers) {
            treeMap.put(flower[0], treeMap.getOrDefault(flower[0], 0) + 1);
            // use end + 1 instead of end
            treeMap.put(flower[1] + 1, treeMap.getOrDefault(flower[1] + 1, 0) - 1);
        }

        TreeMap<Integer, Integer> sum = new TreeMap<>();
        int prev = 0;
        for (Map.Entry<Integer, Integer> entry : treeMap.entrySet()) {
            prev += entry.getValue();
            sum.put(entry.getKey(), prev);
        }

        for (int i = 0; i < n; i++) {
            Map.Entry<Integer, Integer> entry = sum.floorEntry(persons[i]);
            // if entry is null then result[i] = 0
            if (entry != null) result[i] = entry.getValue();
        }
        return result;
    }
}
class Solution {
public:
    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& persons) {
        vector<vector<int>> line; 
        for (auto& f : flowers) {
            line.push_back({f[0], +1}); 
            line.push_back({f[1]+1, -1}); 
        }
        sort(line.begin(), line.end()); 
        int prefix = 0; 
        vector<int> time, vals; 
        for (auto& l : line) {
            time.push_back(l[0]); 
            vals.push_back(prefix += l[1]); 
        }
        vector<int> ans; 
        for (auto& p : persons) {
            auto it = upper_bound(time.begin(), time.end(), p); 
            if (it == time.begin()) ans.push_back(0); 
            else ans.push_back(vals[it - time.begin() - 1]); 
        }
        return ans; 
    }
};
/**
 * @param {number[][]} flowers
 * @param {number[]} persons
 * @return {number[]}
 */
var fullBloomFlowers = function(flowers, persons) {
    // *** IDEATION *** //
    // key observation:
    // total number of flowers see on day i =
    // number of flowers has already bloomed so far on day i - number of flowers already ended ("died") prior to day i

    // find number of flowers already bloomed on day i
    // each flower has a start day
    // start array = [1, 3, 9, 4] for example
    // on day 8, there are 3 flowers bloomed:
    // equivalent to find the number of elements in the "start" array which is less than or equal to 8

    // find number of flowers already ended on day i
    // each flower has an end day
    // end array = [6, 7, 12, 13] for example
    // on day 8, there are 2 flowers already ended:
    // equivalent to find the number of elements in the "end" array which is less than 8
    // equivalent to find the number of elements in the "end" array which is less than or equal to 7

    // both process above can be solved efficiently with binary search on a sorted array
    // hence we need to first build 2 array "start" and "end" and sorted it
    // then apply the formula at the beginning to return the required answer

    // *** IMPLEMENTATION *** //
    // step 1: build the "start" and "end" array
    let start = [];
    let end = [];

    for (let i = 0; i < flowers.length; i++) {
        start[i] = flowers[i][0];
        end[i] = flowers[i][1];
    }

    // step 2: sort the "start" and "end" array
    start.sort((a, b) => a - b);
    end.sort((a, b) => a - b);

    // step 3: apply the observation formula using a binarySearch function
    let res = [];
    for (let j = 0; j < persons.length; j++) {
        res[j] = binarySearch(start, persons[j]) - binarySearch(end, persons[j] - 1);
    }
    return res;

    // step 4: implement the binarySearch function (variant from standard binarySearch)
    function binarySearch(array, k) {
        // array is sorted;
        // obj is to find the number of elements in array which is less than or equal to "k"
        let left = 0;
        let right = array.length - 1;
        let index = -1;

        while (left <= right) {
            let mid = left + Math.floor((right - left) / 2);
            if (k < array[mid]) {
                right = mid - 1;
            } else {
                index = Math.max(index, mid); // record the index whenever k >= array[mid]
                left = mid + 1;
            }
        }

        // all elements with in array from position '0' to position 'index' will be less than or equal to k
        return index + 1;
    }
};
Number of Flowers in Full Bloom