Descriptio Link to heading

2251. Number of Flowers in Full Bloom (Hard)

You are given a 0-indexed 2D integer array flowers, where flowers[i] = [startᵢ, endᵢ] means the iᵗʰ flower will be in full bloom from startᵢ to endᵢ ( inclusive). You are also given a 0-indexed integer array people of size n, where people[i] is the time that the iᵗʰ 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 iᵗʰ person arrives.

Example 1:

Input: flowers = [[1,6],[3,7],[9,12],[4,13]], poeple = [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]], poeple = [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.

Constraints:

  • 1 <= flowers.length <= 5 * 10⁴
  • flowers[i].length == 2
  • 1 <= startᵢ <= endᵢ <= 10⁹
  • 1 <= people.length <= 5 * 10⁴
  • 1 <= people[i] <= 10⁹

Solution Link to heading

Divide the flowers array into two arrays: one representing the time when flowers bloom and the other for the time when they wither, both sorted in ascending order.

Subsequently, for each query, one merely needs to determine how many flowers have bloomed by the current time and how many have withered. Given the sorted nature of these arrays, binary search can be employed for efficient implementation.

Code Link to heading 

class Solution {
  public:
    int upper(vector<int> &arr, int time) {
        int l = 0, r = arr.size();
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (arr[mid] <= time) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }
    int lower(vector<int> &arr, int time) {
        int l = 0, r = arr.size();
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (arr[mid] < time) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }
    vector<int> fullBloomFlowers(vector<vector<int>> &flowers, vector<int> &people) {
        // 二分
        int n = flowers.size();
        vector<int> start(n), end(n);
        for (int i = 0; i < n; ++i) {
            start[i] = flowers[i][0];
            end[i] = flowers[i][1];
        }
        sort(start.begin(), start.end());
        sort(end.begin(), end.end());
        vector<int> ans;
        for (int time : people) {
            int res = upper(start, time) - lower(end, time);
            ans.push_back(res);
        }
        return ans;
    }
};