1
class Solution:
2
    def findMinArrowShots(self, points: List[List[int]]) -> int:
3
        if not points:
4
            return 0
5

6
        # 按气球的右边界升序排列
7
        points.sort(key=lambda x: x[1])
8

9
        count = 1  # 至少一支箭
10
        x_end = points[0][1]  # 当前箭射的位置
11

12
        for point in points:
13
            start = point[0]
14
            if start > x_end:
15
                # 当前气球与上一支箭不重叠，需要额外一支箭
16
                count += 1
17
                x_end = point[1]
18

19
        return count

1
class Solution:
2
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
3
        n = len(intervals)
4
        if not intervals:
5
            return 0
6

7
        # 按右端点升序排序
8
        intervals.sort(key=lambda x: x[1])
9

10
        count = 1  # 至少保留一个不重叠区间
11
        x_end = intervals[0][1]
12

13
        for interval in intervals:
14
            start = interval[0]
15
            if start >= x_end:
16
                # 当前区间不重叠，可以保留
17
                count += 1
18
                x_end = interval[1]
19

20
        # 要删除的区间数 = 总数 - 可保留数
21
        return n - count

1
class Solution:
2
    def partitionLabels(self, s: str) -> List[int]:
3
        # 记录每个字母最后一次出现的位置
4
        last_pos = {ch: i for i, ch in enumerate(s)}
5

6
        res = []
7
        start = end = 0
8

9
        for i, ch in enumerate(s):
10
            # 当前分区最远可以延伸到 ch 的最后位置
11
            end = max(end, last_pos[ch])
12
            if i == end:
13
                # 当前 i 达到分区边界，可以切分
14
                res.append(end - start + 1)
15
                start = i + 1
16

17
        return res