贪心算法435|763|56

435无重叠区间

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if len(intervals) == 1:
            return 0
        count = 0
        sorted_intervals = sorted(intervals, key = lambda x: x[0])
        for i in range(1, len(sorted_intervals)):
            if sorted_intervals[i][0] < sorted_intervals[i - 1][1]:
                count += 1
                sorted_intervals[i][1] = min(sorted_intervals[i][1], sorted_intervals[i - 1][1])
        return count

763划分字母区间

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        count = [0] * 26
        for i in range(len(s)):
            cur = s[i]
            count[ord(cur) - ord("a")] = i
        left = 0
        right = 0
        result = []
        for i in range(len(s)):
            cur = s[i]
            index = ord(cur) - ord("a")
            if right < count[index]:
                right = count[index]
            if right == i:
                result.append(right - left + 1)
                left = right + 1
        return result

56合并区间

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if len(intervals) == 1:
            return intervals
        result = []
        sorted_intervals = sorted(intervals, key = lambda x: x[0])
        result.append(sorted_intervals[0])
        for i in range(1, len(sorted_intervals)):
            if sorted_intervals[i][0] <= result[-1][1]:
                result[-1][1] = max(sorted_intervals[i][1], result[-1][1])
            else:
                result.append(sorted_intervals[i])
        return result