LC2251 花期内花的数目

标签：people int List 花期 差分 LC2251 diff flowers 内花

方法一：差分

因为是先修改后查询，很容易想到差分，但因为数据值域 \([-10^9,10^9]\) 过大，所以不能使用差分数组，而应用 map 进行存储，如代码所示：

map<int, int> diff;
// 正常进行差分操作
for(auto& f : flowers) {
    diff[f[0]]++;
    diff[f[1] + 1]--;
}
// do something
auto it = diff.begin();
int sum = 0;
for(int i : id) {
    // 略过了中间的位置
    while(it != diff.end() && it->first <= people[i]) {
        sum += it++->second;
    }
    people[i] = sum;
}

注意给出的 \(people\) 数组是无序的，需要 iota 一个 \(id\) 数组，按照 \(people\) 排序。

方法二：二分

分别排序区间的左右端点 \(s,t\)，对每个 \(people_i\) 二分查找前面有多少左端点、右端点，即开花数-凋谢数。

下面是一份 python 代码，非常简练：

class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
        starts = sorted(s for s, _ in flowers)
        ends = sorted(e for _, e in flowers)
        return [bisect_right(starts, p) - bisect_left(ends, p) for p in people]

THE END

参考：灵茶山艾府 https://leetcode.cn/problems/number-of-flowers-in-full-bloom/

标签：people,int,List,花期,差分,LC2251,diff,flowers,内花
From： https://www.cnblogs.com/th19/p/17736002.html