题目描述
给你一个下标从 0 开始的二维整数数组 flowers
,其中 flowers[i] = [start_i, end_i]
表示第 i
朵花的 花期 从 start_i
到 end_i
(都 包含)。同时给你一个下标从 0 开始大小为 n
的整数数组 persons
,persons[i]
是第 i
个人来看花的时间。
请你返回一个大小为 n
的整数数组 answer
,其中 answer[i]
是第 i
个人到达时在花期内花的 数目。
样例
输入:flowers = [[1,6],[3,7],[9,12],[4,13]], persons = [2,3,7,11]
输出:[1,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 <= start_i <= end_i <= 10^9
1 <= persons.length <= 5 * 10^4
1 <= persons[i] <= 10^9
算法
(离散化,差分前缀和) $O((n + p) \log (n + p))$
- 将每朵花的 $start_i$ 和 $end_i$,以及 $persons_i$ 进行离散化,将原值区间按从小到大的顺序映射到从 $1$ 开始的区间。
- 离散化后,将每朵花的花期按照差分的方式,放到差分数组 $sum$ 上。
- 求差分数组的前缀和。
- 对于每个人,取离散化后的到达时间上差分数组 $sum$ 的值。
时间复杂度
- 离散化的时间复杂度为 $O((n + p) \log (n + p))$。
- 预处理差分数组的时间复杂度为 $O(n + p + n \log (n + p))$。
- 求答案的时间复杂度为 $O(p \log (n + p))$。
- 故总时间复杂度为 $O((n + p) \log (n + p))$。
空间复杂度
- 需要 $O(n + p)$ 的额外空间存储离散化数组,差分数组和答案。
C++ 代码
class Solution {
public:
vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& persons) {
const int n = flowers.size();
vector<int> seen;
for (const auto &f : flowers) {
seen.push_back(f[0]);
seen.push_back(f[1]);
}
for (int p : persons)
seen.push_back(p);
sort(seen.begin(), seen.end());
int m = unique(seen.begin(), seen.end()) - seen.begin();
seen.resize(m);
vector<int> sum(m + 1, 0);
for (const auto &f : flowers) {
int l = lower_bound(seen.begin(), seen.end(), f[0]) - seen.begin();
int r = lower_bound(seen.begin(), seen.end(), f[1]) - seen.begin();
sum[l]++; sum[r + 1]--;
}
for (int i = 1; i < m + 1; i++)
sum[i] += sum[i - 1];
vector<int> ans;
for (int p : persons) {
int t = lower_bound(seen.begin(), seen.end(), p) - seen.begin();
ans.push_back(sum[t]);
}
return ans;
}
};