# 2251. 花期内花的数目 (Hard)

## 问题描述

[2251. 花期内花的数目][link] (Hard)

[link]: https://leetcode.cn/problems/number-of-flowers-in-full-bloom/

给你一个下标从 **0** 开始的二维整数数组 `flowers` ，其中 `flowers[i] = [startᵢ, endᵢ]` 表示第 `i` 朵
花的 **花期** 从 `startᵢ` 到 `endᵢ` （都 **包含**）。同时给你一个下标从 **0** 开始大小为 `n` 的整数
数组 `people` ， `people[i]` 是第 `i` 个人来看花的时间。

请你返回一个大小为 `n` 的整数数组 `answer` ，其中 `answer[i]` 是第 `i` 个人到达时在花期内花的 **数目
** 。

**示例 1：**

![](https://pic-upyun.zwyyy456.tech/smms/2023-12-26-065454.jpg)

```
输入：flowers = [[1,6],[3,7],[9,12],[4,13]], people = [2,3,7,11]
输出：[1,2,2,2]
解释：上图展示了每朵花的花期时间，和每个人的到达时间。
对每个人，我们返回他们到达时在花期内花的数目。
```

**示例 2：**

![](https://pic-upyun.zwyyy456.tech/smms/2023-12-26-65458.jpg)

```
输入：flowers = [[1,10],[3,3]], people = [3,3,2]
输出：[2,2,1]
解释：上图展示了每朵花的花期时间，和每个人的到达时间。
对每个人，我们返回他们到达时在花期内花的数目。
```

**提示：**

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

## 解题思路

### 二分
将 `flowers` 数组拆分成花朵开花时间的数组和枯萎时间的数组，均按照时间升序排列。

那么，对每一个查询，我们只需要查询到当前时间，有多少花朵盛开，以及有多少花朵枯萎即可，由于是有序数组，可以使用二分查找来实现。

### 差分

差分需要对花朵的盛开与枯萎时间进行离散化，使其分别对应一个下标。

离散化的方案类似于 [327. 区间和的个数](https://leetcode.cn/problems/count-of-range-sum/)

## 代码

```cpp
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;
    }
};
```