贪心算法860|406|452

860柠檬水找零

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five = 0
        ten = 0
        for i in range(len(bills)):
            if bills[i] == 5:
                five += 1
            elif bills[i] == 10:
                if five > 0:
                    five -= 1
                    ten += 1
                else:
                    return False
            elif bills[i] == 20:
                if five > 0 and ten > 0:
                    five -= 1
                    ten -= 1
                elif five >= 3:
                    five -= 3
                else:
                    return False
        return True

406根据身高重建队列

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        sorted_people = sorted(people, key = lambda x: (-x[0], x[1]))
        for i in range(len(sorted_people)):
            if sorted_people[i][1] != i:
                index = sorted_people[i][1]
                temp = sorted_people.pop(i)
                sorted_people.insert(index, temp)
        return sorted_people

452用最少数量的箭引爆气球

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