花期内花的数目

标签: 数组 哈希表 二分查找 有序集合 前缀和 排序

难度: 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 * 104
  • flowers[i].length == 2
  • 1 <= starti <= endi <= 109
  • 1 <= people.length <= 5 * 104
  • 1 <= people[i] <= 109

Submission

运行时间: 151 ms

内存: 39.4 MB

class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
        # flowers.sort()
        # result = []
        # def checkin(time,flow):
        #     if (time>=flow[0]) and (time <= flow[1]): 
        #         return True
        # for j in range(len(people)):
        #     result.extend([0])
        #     for i, x in enumerate(flowers):
        #         if x[0] > people[j]:
        #             break
        #         if checkin(people[j], x):
        #             result[j] += 1
        # return result
        start_times = sorted([f[0] for f in flowers])
        end_times = sorted([f[1] for f in flowers])
        n = len(flowers)
        result = []

        for p in people:
            # 使用二分查找找到第一个结束时间大于等于到达时间p的花的索引
            start_idx = bisect_right(start_times, p)
            end_idx = bisect_left(end_times, p)
            # 计算在花期内的花的数量
            bloom_count = start_idx - end_idx
            result.append(bloom_count)

        return result

Explain

本题解使用了排序和二分查找的方法来高效地计算每个人到达时在花期内的花的数目。首先，从输入的flowers数组中提取所有花的开始时间和结束时间，并将它们分别排序。使用这两个排序后的数组，可以快速地通过二分查找确定对于任意给定的时间点p，有多少花已经开始开放，以及有多少花已经结束开放。具体地，对于每个人的到达时间p，使用二分查找在开始时间数组中找到第一个大于p的位置（start_idx），这表示直到时间p为止已经开始开放的花的数量；在结束时间数组中找到第一个大于或等于p的位置（end_idx），这表示直到时间p刚好还没有结束开放的花的数量。花期内的花的数量即为 start_idx - end_idx。

时间复杂度: O(n log n + m log n)

空间复杂度: O(n + m)

class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
        # 对花的开始和结束时间进行排序
        start_times = sorted([f[0] for f in flowers])
        end_times = sorted([f[1] for f in flowers])
        n = len(flowers)
        result = []

        for p in people:
            # 使用二分查找找到第一个开始时间大于p的花的索引
            start_idx = bisect_right(start_times, p)
            # 使用二分查找找到第一个结束时间大于等于p的花的索引
            end_idx = bisect_left(end_times, p)
            # 计算在花期内的花的数量
            bloom_count = start_idx - end_idx
            result.append(bloom_count)

        return result

Explore

在这个算法中，`start_idx`和`end_idx`是通过二分查找计算得到的，它们帮助确定在任意时间点p有多少花处于开放状态。首先，`start_times`数组包含所有花的开放开始时间，经过排序后，使用`bisect_right`函数查找到第一个大于时间p的元素的索引`start_idx`。`bisect_right`返回的是可以插入时间点p的最右侧位置，因此`start_idx`的值代表了在时间p之前（包括p时刻刚好开始开放的花）开始开放的花的数量。其次，`end_times`数组包含所有花的开放结束时间，同样经过排序。使用`bisect_left`查找第一个大于或等于时间p的元素的索引`end_idx`。`bisect_left`返回的是可以插入时间点p的最左侧位置，因此`end_idx`的值代表了在时间p之前结束开放的花的数量（不包括p时刻结束的花）。因此，处于开放状态的花的总数为`start_idx - end_idx`，这个结果是因为我们从开始开放的花的总数中减去了在p时刻还未结束开放的花的数量。