LeetCode 2251. Number of Flowers in Full Bloom

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& persons) {
        map<int, int> diff;
        for (auto &f : flowers) ++diff[f[0]], --diff[f[1] + 1];
        int n = persons.size();
        vector<int> id(n);
        iota(id.begin(), id.end(), 0);
        sort(id.begin(), id.end(), [&](int i, int j) {
            return persons[i] < persons[j];
        });
        vector<int> ans(n);
        auto it = diff.begin();
        int s = 0;
        for (int i : id) {
            while (it != diff.end() && it->first <= persons[i])
                s += it++->second;
            ans[i] = s;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& persons) {
        int n = flowers.size();
        vector<int> s(n), e(n);
        for (int i = 0; i < n; ++i) s[i] = flowers[i][0], e[i] = flowers[i][1];
        sort(s.begin(), s.end());
        sort(e.begin(), e.end());
        int m = persons.size();
        vector<int> ans(m);
        for (int i = 0; i < m; ++i) {
            ans[i] = (upper_bound(s.begin(), s.end(), persons[i]) - s.begin())
                - (lower_bound(e.begin(), e.end(), persons[i]) - e.begin());
        }
        return ans;
    }
};