贪心算法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