给你一个下标从 0 开始的二维整数数组 flowers
其中 flowers[i] = [starti, endi] 表示第 i 朵花的花期从 starti 到 endi
同时给你一个下标从 0 开始大小为 n 的整数数组 people ，people[i] 是第 i 个人来看花的时间
请你返回一个大小为 n 的整数数组 answer ，其中 answer[i]是第 i 个人到达时在花期内花的数目
1. 合并排序 + 离线查询
插入点和查询点合并
class Solution {
public:
vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& people) {
//离线查询，分别标识天数，开花、人、死掉，以及人对应的位置结果标识
vector<vector<int>> search;
int curflower = 0;//记录当前花的数目
for(auto &flower:flowers){
search.push_back(vector<int>{flower[0],1,-1});
search.push_back(vector<int>{flower[1],3,-1});
}
for(int i=0;i<people.size();i++)
search.push_back(vector<int>{people[i],2,i});
sort(search.begin(),search.end(),[&](const vector<int>&a,const vector<int>&b ){
if(a[0]==b[0]) return a[1]<b[1];
return a[0]<b[0];
});
vector<int> res(people.size());
for(auto &s:search){
if(s[1]==1) curflower++;
if(s[1]==2) res[s[2]] = curflower;
if(s[1]==3) curflower--;
}
return res;
}
};
2. 不合并排序 + 离线查询
插入点和查询点不合并
class Solution {
public:
vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& people) {
//离线查询，分别标识天数，开花、人、死掉，以及人对应的位置结果标识
vector<vector<int>> search;
int curflower = 0;//记录当前花的数目
for(auto &flower:flowers){
search.push_back(vector<int>{flower[0],1});
search.push_back(vector<int>{flower[1]+1,-1});
}
sort(search.begin(),search.end());
vector<int> index(people.size());
iota(index.begin(),index.end(),0);
sort(index.begin(),index.end(),[&](int a,int b){
return people[a]<people[b];
});
int sidx = 0;
vector<int> res(people.size());
for(auto idx:index){
while(sidx<search.size()&&search[sidx][0]<=people[idx])
curflower+=search[sidx++][1];
res[idx] = curflower;
}
return res;
}
};
3. 差分 + 离线查询
本质上是利用红黑树的有序，进行查询
class Solution {
public:
vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& persons) {
map<int, int> cnt;
for (auto &flower : flowers) {
cnt[flower[0]]++;
cnt[flower[1] + 1]--;
}
int n = persons.size();
vector<int> indices(n);
iota(indices.begin(), indices.end(), 0);
sort(indices.begin(), indices.end(), [&](int a, int b) {
return persons[a] < persons[b];
});
vector<int> ans(n);
int curr = 0;
auto it = cnt.begin();
for (int x : indices) {
while (it != cnt.end() && it->first <= persons[x]) {
curr += it->second;
it++;
}
ans[x] = curr;
}
return ans;
}
};
4. 排序 + 二分
直接二分求开花和落花的个数
class Solution {
public:
vector<int> fullBloomFlowers(vector<vector<int>> &flowers, vector<int> &persons) {
int n = flowers.size();
vector<int> starts(n), ends(n);
for (int i = 0; i < n; ++i) {
starts[i] = flowers[i][0];
ends[i] = flowers[i][1];
}
sort(starts.begin(), starts.end());
sort(ends.begin(), ends.end());
int m = persons.size();
vector<int> ans(m);
for (int i = 0; i < m; ++i) {
int x = upper_bound(starts.begin(), starts.end(), persons[i]) - starts.begin();
int y = lower_bound(ends.begin(), ends.end(), persons[i]) - ends.begin();
ans[i] = x - y;
}
return ans;
}
};
5. 离散化 + 树状数组
class Solution {
public:
vector<int> fullBloomFlowers(vector<vector<int>> &flowers, vector<int> &persons) {
map<int,int> m;
//进行离散化
for(auto &flower:flowers){
m[flower[0]]++;
m[flower[1]+1]++;
}
for(auto person:persons)
m[person]++;
int idx = 1;
for(auto &[key,val]:m)
val = idx++;
//初始化树
n = m.size();
tree.resize(n+1,0);
//对插入点进行插入更新
for(auto &flower:flowers){
update(m[flower[0]],1);
update(m[flower[1]+1],-1);
}
//进行查询
for(auto &person:persons)
person = getsum(m[person]);
return persons;
}
vector<int> tree;
int n;
int lowbit(int x){//求二进制化最后一位的值
return x&(-x);
}
void update(int i,int k){ //在i位置加上k，O(logn)复杂度单点修改
while(i<=n){//更新子树上所有值
tree[i]+=k;
i+=lowbit(i);//移动到父亲节点
}
}
long long getsum(int i){ //求数组前i项的和
long long res=0;
while(i>0){//O(logn)求前缀和
res+=tree[i];
i-=lowbit(i);//移动到前一棵子树（子区间）
}
return res;
}
};