题目
样例
数据
1 <= flowers.length <= 5 * 104
1 <= starti <= endi <= 109
1 <= persons.length <= 5 * 104
1 <= persons[i] <= 109
题解
map差分 + 双指针
思路：
class Solution { public: vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& persons) { map<int, int> mp; for (auto &x: flowers) mp[x[0]]++, mp[x[1] + 1]--; vector<int> id(persons.size()); iota(id.begin(), id.end(), 0); sort(id.begin(), id.end(), [&](int i, int j){ return persons[i] < persons[j]; }); vector<int> ans(persons.size()); auto it = mp.begin(); int sum = 0; for (int i = 0; i < id.size(); i++) { while(it != mp.end() && it->first <= persons[id[i]]) sum += it++->second; ans[id[i]] = sum; } return ans; } };
二分（清晰透彻）
思路：
- 正在开的花的个数 = 所有在此时间节点及之前开放的花的个数 - 在时间节点之前凋谢的花的个数
class Solution { public: vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& persons) { int n = flowers.size(); vector<int> open(n), close(n); for (int i = 0; i < n; i++) open[i] = flowers[i][0], close[i] = flowers[i][1]; sort(open.begin(), open.end()); sort(close.begin(), close.end()); vector<int> ans; for (int i = 0; i < persons.size(); i++) { int now = persons[i]; int op = upper_bound(open.begin(), open.end(), now) - open.begin(); int cl = upper_bound(close.begin(), close.end(), now - 1) - close.begin(); ans.push_back(op - cl); } return ans; } };
差分 + 树状数组 + 哈希
哈希树状数组
注释正常思路，对开花，谢花，人到的时间点都标记，排序。
但数据太大，t r {tr}tr数组维护不了1e9的长度
时间开销大
class Solution { public: static constexpr int N = 1e9 + 7; // int tr[N]; unordered_map<int, int> tr; void add(int x, int c = 1) { for (; x <= N; x += x & -x) tr[x] += c; } int sum(int x) { int res = 0; for (; x; x -= x & -x) res += tr[x]; return res; } // #define INF 0x3f3f3f3f vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& persons) { int n = flowers.size(); // vector<pair<int, int>> v; // for (int i = 0; i < n; i++) v.push_back({flowers[i][0], -INF}), v.push_back({flowers[i][1], INF}); // for (int i = 0; i < persons.size(); i++) v.push_back({persons[i], i}); // sort(v.begin(), v.end()); for (auto &x: flowers) add(x[0], 1), add(x[1] + 1, -1); // 从这之后少1，差分嘛 vector<int> ans(persons.size()); for (int i = 0; i < persons.size(); i++) { // auto x = v[i]; // if(x.second == -INF) add(x.first, 1); // else if(x.second == INF) add(x.first + 1, -1); // else ans[x.second] = sum(x.first); ans[i] = sum(persons[i]); } return ans; } };
离散化 + 前缀和 （简洁明了）
思路：
离散化（map）后，cnt<=3∗5e4
直接前缀和求得答案。
class Solution { public: map<int, int> a, id; int s[150010]; int cnt = 0; vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& persons) { for (auto &x: flowers) a[x[0]] = 1, a[x[1] + 1] = 1; for (auto &x: persons) a[x] = 1; for (auto &x: a) id[x.first] = ++cnt; for (auto &x: flowers) s[id[x[0]]]++, s[id[x[1] + 1]]--; for (int i = 1; i <= cnt; i++) s[i] += s[i - 1]; vector<int> res; for (auto &x: persons) res.push_back(s[id[x]]); return res; } };
