C++ 程序设计：花期内花的数目（LeetCode：2251）

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

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

示例 1：

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

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

提示：

1 <= flowers.length <= 5 * 10^4
flowers[i].length == 2
1 <= starti <= endi <= 10^9
1 <= persons.length <= 5 * 10^4
1 <= persons[i] <= 10^9

思路：经典差分数组求前缀和思想。不过这题的难点在于时间区间较大，因此无法通过开辟常规数组解决，一种可取得方式是采用map映射区间端点的方式。求前缀和方式和常规数组没差，我们只需知道各个区间端点的变化量即可。此外，我们需要对查询数组按照时间排序，进行离线查询。

class Solution {

public:

static bool comp(vector<int>& a, vector<int>& b) {

if (a[1] == b[1])

return a[0] < b[0];

return a[1] < b[1];

}

vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& persons) {

map<int, int> diff;

int n = persons.size();

vector<int> ans(n);

vector<pair<int, int>> arr;

for (int i = 0; i < n; ++i)

arr.emplace_back(make_pair(persons[i], i));

sort(arr.begin(), arr.end());

for (int i = 0; i < flowers.size(); ++i) {

++diff[flowers[i][0]];

--diff[flowers[i][1] + 1];

}

int sum = 0;

auto it = diff.begin();

for (int i = 0; i < n; ++i) {

while (it != diff.end() && it->first <= arr[i].first)

sum += it++->second;

ans[arr[i].second] = sum;

}

return ans;

}

};

相关知识

C++ 程序设计：花期内花的数目（LeetCode：2251）
leetcode 6044. 花期内花的数目 —（每日一难day1）
2251. 花期内花的数目
2251. 花期内花的数目（cpp内置二分查找）
花期内花的数目【离散化+前缀和+差分】
LeetCode
力扣题目训练：605
花的形态与结构课件.ppt
一份水稻花器官突变体的形态发生、性状遗传分析及相关基因的分子标记定位
切尔西花展 长城展览

网址: C++ 程序设计：花期内花的数目（LeetCode：2251） https://www.huajiangbk.com/newsview42863.html