问题描述 链接到标题

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

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

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

示例 1：

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

示例 2：

输入：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. 区间和的个数

代码 链接到标题 

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