代码随想录算法训练营 Day 26

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if len(points) == 0:
            return 0
        
        points.sort(key=lambda x:x[0])
        res = 1
        curr_right = points[0][1]
        for i in range(1, len(points)):
            if points[i][0] > curr_right:
                res += 1
                curr_right = points[i][1]
            else:
                curr_right = min(curr_right, points[i][1])
        
        return res

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if len(points) == 0:
            return 0
        
        points.sort(key=lambda x:-x[1])

        res = 1
        curr_left = points[0][0]
        for i in range(1, len(points)):
            if points[i][1] < curr_left:
                res += 1
                curr_left = points[i][0]
            else:
                curr_left = max(curr_left, points[i][0])

        return res

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if len(intervals) == 0:
            return 0
        
        intervals.sort(key=lambda x:x[1])

        count = 1
        curr_right = intervals[0][1]
        for i in range(1, len(intervals)):
            if intervals[i][0] >= curr_right:
                count += 1
                curr_right = intervals[i][1]
            else:
                curr_right = min(intervals[i][1], curr_right)
        
        return len(intervals) - count

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        hashmap = {}
        for i in range(len(s)):
            hashmap[s[i]] = i

        res = []
        end = 0
        start = 0
        for i in range(len(s)):
            # 先求最大值，再考虑是否匹配（特殊情况：第一个substring只含有首字母）
            end = max(end, hashmap[s[i]])
            if i == end:
                res.append(end - start + 1)
                start = i + 1

        return res