35天【代码随想录算法训练营34期】第八章 贪心算法 part04 ( ● 860.柠檬水找零 ● 406.根据身高重建队列 ● 452. 用最少数量的箭引爆气球 )

860.柠檬水找零

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        amt_five = 0
        amt_ten = 0
        amt_twenty = 0

        for i in bills:
            if i == 5:
                amt_five += 1
            elif i == 10:
                amt_ten += 1
                if amt_five == 0:
                    return False
                else:
                    amt_five -= 1
            elif i == 20:
                amt_twenty += 1
                if amt_five > 0 and amt_ten > 0:
                    amt_ten -= 1
                    amt_five -= 1
                elif amt_ten == 0 and amt_five >= 3:
                    amt_five -= 3
                else:
                    return False
        return True

406.根据身高重建队列
太厉害了，我自己做不出来

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x: (-x[0], x[1]))
        ans = []

        for i in people:
            ans.insert(i[1], i)

        return ans

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

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