2023-09-28力扣每日一题-差分

链接：

2251. 花期内花的数目

题意

n朵花，有n个花期，m个人在m个时间来，求每个时间有多少朵花

解：

通过差分确定一个时间段内的花数量

再通过离线查询（因为返回答案数组）进行记忆存储，只需要一次遍历

实际代码：

#include
using namespace std;
vector fullBloomFlowers(vector>& flowers, vector& people)
{
    mapcf;
    for(const auto& flower:flowers)
	{
		cf[flower[0]]++;
		cf[flower[1]+1]--;
	}
	
	vectorpeople_sort=people;
	sort(people_sort.begin(),people_sort.end());
	mapS2S;
	
	int num=0;
	auto it=cf.begin();
	for(auto p:people_sort)
	{
		while(it!=cf.end() && it->first<=p)
		{
			num+=it->second;
			it++;
		}
		S2S[p]=num;
	}
	
	vectorans;
	for(auto p:people)
	{
		ans.push_back(S2S[p]);
	}
	return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

限制：

• 1 <= flowers.length <= 5 * 104
• flowers[i].length == 2
• 1 <= starti <= endi <= 109
• 1 <= people.length <= 5 * 104
• 1 <= people[i] <= 109