Hard

题目描述

给你一个下标从 0 开始的二维整数数组 flowers，其中 flowers[i] = [starti, endi] 表示第 i 朵花会在 starti 时刻开始盛开，在 endi 时刻结束盛开（包含边界）。同时给你一个下标从 0 开始、大小为 n 的整数数组 people，其中 people[i] 是第 i 个人来看花的时刻。

请你返回一个大小为 n 的整数数组 answer，其中 answer[i] 是第 i 个人到达时刻，正处于盛开状态的花朵数目。

示例 1：

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

示例 2：

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

提示：

  • 1 <= flowers.length <= 5 * 10^4
  • flowers[i].length == 2
  • 1 <= starti <= endi <= 10^9
  • 1 <= people.length <= 5 * 10^4
  • 1 <= people[i] <= 10^9

解题思路

解题思路

这道题的核心思想是：在时刻 t，盛开的花朵数量 = 已经开始盛开的花朵数量 - 已经结束盛开的花朵数量。

方法一：差分数组（推荐） 利用差分思想，在开花时间点 +1，在结束时间的下一个时间点 -1。然后通过前缀和还原每个时间点的花朵数量。由于时间范围很大，需要进行坐标压缩。

方法二：二分查找 分别提取所有花朵的开始时间和结束时间并排序。对于每个人的到达时间，通过二分查找：

  • 找到已经开始盛开的花朵数量
  • 找到已经结束盛开的花朵数量
  • 两者相减得到当前盛开的花朵数量

这里采用二分查找的方法，时间复杂度更优且实现简单。

核心步骤：

  1. 分别提取并排序所有花朵的开始时间和结束时间
  2. 对每个人的到达时间，使用 upper_bound 计算已开始和已结束的花朵数量
  3. 相减得到当前盛开的花朵数量

代码实现

class Solution {
public:
    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& people) {
        vector<int> starts, ends;
        
        // 提取开始和结束时间
        for (auto& flower : flowers) {
            starts.push_back(flower[0]);
            ends.push_back(flower[1]);
        }
        
        // 排序
        sort(starts.begin(), starts.end());
        sort(ends.begin(), ends.end());
        
        vector<int> result;
        
        for (int time : people) {
            // 已经开始盛开的花朵数量
            int started = upper_bound(starts.begin(), starts.end(), time) - starts.begin();
            // 已经结束盛开的花朵数量
            int ended = upper_bound(ends.begin(), ends.end(), time - 1) - ends.begin();
            
            result.push_back(started - ended);
        }
        
        return result;
    }
};

class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
        import bisect
        
        # 提取开始和结束时间
        starts = [flower[0] for flower in flowers]
        ends = [flower[1] for flower in flowers]
        
        # 排序
        starts.sort()
        ends.sort()
        
        result = []
        
        for time in people:
            # 已经开始盛开的花朵数量
            started = bisect.bisect_right(starts, time)
            # 已经结束盛开的花朵数量
            ended = bisect.bisect_right(ends, time - 1)
            
            result.append(started - ended)
        
        return result

public class Solution {
    public int[] FullBloomFlowers(int[][] flowers, int[] people) {
        List<int> starts = new List<int>();
        List<int> ends = new List<int>();
        
        // 提取开始和结束时间
        foreach (var flower in flowers) {
            starts.Add(flower[0]);
            ends.Add(flower[1]);
        }
        
        // 排序
        starts.Sort();
        ends.Sort();
        
        int[] result = new int[people.Length];
        
        for (int i = 0; i < people.Length; i++) {
            int time = people[i];
            
            // 已经开始盛开的花朵数量
            int started = UpperBound(starts, time);
            // 已经结束盛开的花朵数量
            int ended = UpperBound(ends, time - 1);
            
            result[i] = started - ended;
        }
        
        return result;
    }
    
    private int UpperBound(List<int> arr, int target) {
        int left = 0, right = arr.Count;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

var fullBloomFlowers = function(flowers, people) {
    // 提取开始和结束时间
    const starts = flowers.map(flower => flower[0]);
    const ends = flowers.map(flower => flower[1]);
    
    // 排序
    starts.sort((a, b) => a - b);
    ends.sort((a, b) => a - b);
    
    const result = [];
    
    for (const time of people) {
        // 已经开始盛开的花朵数量
        const started = upperBound(starts, time);
        // 已经结束盛开的花朵数量
        const ended = upperBound(ends, time - 1);
        
        result.push(started - ended);
    }
    
    return result;
    
    function upperBound(arr, target) {
        let left = 0, right = arr.length;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (arr[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n log n + m log n)
空间复杂度O(n)

其中 n 是 flowers 数组的长度，m 是 people 数组的长度。

  • 排序需要 O(n log n)
  • 每次二分查找需要 O(log n)，总共 m 次查询
  • 空间复杂度主要用于存储开始和结束时间数组

相关题目