花期内的花的数目-526互联

2251.花期内的花的数目
看到题目的第一想法是桶排序，但是想想肯定会超时，在题解区看到了这么一种解法，感觉很有意思，就记录一下。
要统计某一时间内多少花开放，也就是统计某一时间有多少花开放在它之前，结束在它之后。因为一朵花的开始一定是比结束早的，所以并不需要关心匹配问题。
使用两个数组分别存储花开与花谢的日期，排序后使用二分法即可快速得到某一日期的花开数量。

优点：不用存储花期的对应关系。
缺点：不能确定是哪些花在这天会开放。

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;
    }
};

数目