因此#xff0c;我们只需要将basket按照其capacit…Leetcode

3479.

这一题思路本质上就是考察每一个水果被考察时找到第一个满足条件且未被使用的basket。

因此我们只需要将basket按照其capacity进行排序此时考察每一个水果时我们用二分法即可快速找到某一个坐标idx满足其后任意一个箱子都可以用于盛放该水果。

此时我们就要从对应的这些篮子当中找到其原始的坐标最小的位置即可。

而这就是一个典型的segment

对于segment

tree网上已经有不少相关的介绍了我自己也写过一篇小文章作为备忘经典算法Segment

Tree因此这里就不过多展开了有兴趣的读者可以自行去了解一下。

代码实现

self.feature_func(self.tree[idx],

self.tree[idx

1:nodes.append(self.tree[lb])lb

1if

0:nodes.append(self.tree[rb])rb

1lb

rb:nodes.append(self.tree[rb])return

Solution:def

enumerate(baskets)])ordered_baskets_capacity

[x[0]

ordered_baskets]ordered_baskets_index

[x[1]

SegmentTree(ordered_baskets_index)ans

0for

bisect.bisect_left(ordered_baskets_capacity,

fruit)if

bisect.bisect_left(ordered_baskets,

basket)segment_tree.update(idx,

n)return