README.md

2251. 花期内花的数目

English Version

题目描述

给你一个下标从 0 开始的二维整数数组 flowers ，其中 flowers[i] = [starti, endi] 表示第 i 朵花的 花期 从 starti 到 endi （都 包含）。同时给你一个下标从 0 开始大小为 n 的整数数组 persons ，persons[i] 是第 i 个人来看花的时间。

请你返回一个大小为 n 的整数数组 answer ，其中 answer[i]是第 i 个人到达时在花期内花的 数目 。

 

示例 1：

输入：flowers = [[1,6],[3,7],[9,12],[4,13]], persons = [2,3,7,11]
输出：[1,2,2,2]
解释：上图展示了每朵花的花期时间，和每个人的到达时间。
对每个人，我们返回他们到达时在花期内花的数目。

示例 2：

输入：flowers = [[1,10],[3,3]], persons = [3,3,2]
输出：[2,2,1]
解释：上图展示了每朵花的花期时间，和每个人的到达时间。
对每个人，我们返回他们到达时在花期内花的数目。

 

提示：

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

解法

离散差分+离散查询

Python3

Java

TypeScript

function fullBloomFlowers(flowers: number[][], persons: number[]): number[] {
    // 离散差分
    let hashMap = new Map();
    for (let [start, end] of flowers) {
        end++;
        hashMap.set(start, (hashMap.get(start) || 0) + 1);
        hashMap.set(end, (hashMap.get(end) || 0) - 1);
    }
    for (let p of persons) {
        if (!hashMap.has(p)) {
            hashMap.set(p, 0);
        }
    }
    let keys = Array.from(hashMap.keys()).sort((a, b) => a - b);
    let pre = 0;
    for (let k of keys) {
        pre += hashMap.get(k);
        hashMap.set(k, pre);
    }
    // 离散查询
    let ans = persons.map(v => hashMap.get(v));
    return ans;
}

...