How do I solve the Number of Flowers in Full Bloom problem efficiently?

The key to solving this problem efficiently is sorting both the flowers and the people by time. After sorting, binary search can be used to count how many flowers are in bloom at each person's arrival time.

What is the time complexity of the Number of Flowers in Full Bloom problem?

The time complexity is O((n + m) \cdot \log{n}), where n is the number of flowers and m is the number of people, primarily due to sorting and binary search operations.

Can I use a brute-force solution for this problem?

While a brute-force solution is possible, it will be inefficient for larger inputs due to the high number of comparisons required. The optimal solution uses sorting and binary search to reduce the time complexity.

How do I apply binary search to the Number of Flowers in Full Bloom problem?

Binary search can be applied to find the number of flowers that have started blooming before each person's arrival time, allowing you to count the blooming flowers efficiently.

What data structures are helpful for solving this problem?

Helpful data structures include sorted arrays for the bloom times, binary search for efficient lookup, and hash maps for storing the results of each person's query.

#2251

Hard

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

花期内花的数目

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

数组哈希表二分查找排序前缀和

题目描述

给你一个下标从 0 开始的二维整数数组 flowers ，其中 flowers[i] = [start_i, end_i] 表示第 i 朵花的花期从 start_i 到 end_i （都包含）。同时给你一个下标从 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⁴
flowers[i].length == 2
1 <= start_i <= end_i <= 10⁹
1 <= people.length <= 5 * 10⁴
1 <= people[i] <= 10⁹

lightbulb

解题思路

方法一：排序 + 二分查找

我们将花按照开始时间和结束时间分别排序，然后对于每个人，我们可以使用二分查找来找到他们到达时在花期内花的数目。就是说，找出在每个人到达时，已经开花的花的数目，减去在每个人到达时，已经凋谢的花的数目，即可得到答案。

时间复杂度 $O((m + n) \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 和 $m$ 分别是数组 $\textit{flowers}$ 和 $\textit{people}$ 的长度。

1

2

3

4

5

6

7

class Solution:
    def fullBloomFlowers(
        self, flowers: List[List[int]], people: List[int]
    ) -> List[int]:
        start, end = sorted(a for a, _ in flowers), sorted(b for _, b in flowers)
        return [bisect_right(start, p) - bisect_left(end, p) for p in people]

speed

复杂度分析

指标	值
时间	O((n + m) \cdot \log{n})
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Look for familiarity with binary search and sorting techniques.
question_mark
Assess the candidate's ability to handle large input sizes with an optimized approach.
question_mark
Evaluate whether the candidate can effectively apply hash maps and binary search together.

warning

常见陷阱

外企场景

error
Forgetting to sort the flower intervals and people's arrival times, which will lead to inefficient solutions.
error
Not utilizing binary search or hash maps, which can result in a slower, less optimized solution.
error
Misunderstanding the problem by assuming all flowers are blooming at every time point, leading to incorrect results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider adding extra constraints, such as limiting the number of flowers or the range of bloom times.
arrow_right_alt
Explore how the solution changes if the flowers' blooming times are not continuous, adding complexity to the bloom intervals.
arrow_right_alt
Alter the problem to calculate the number of flowers in bloom over a specific range of times instead of for individual people.

help

常见问题

外企场景

继续练习

#2713 矩阵中严格递增的单元格数 #2234 花园的最大总美丽值 #2271 毯子覆盖的最多白色砖块数