LeetCode Day 35 Greedy Algorithm (4/6)

4th Day of greedy algorithm practice.

Question 1

860. Lemonade Change

At a lemonade stand, each lemonade costs $5. Customers are standing in a queue to buy from you and order one at a time (in the order specified by bills). Each customer will only buy one lemonade and pay with either a $5, $10, or $20 bill. You must provide the correct change to each customer so that the net transaction is that the customer pays $5.

Note that you do not have any change in hand at first.

Given an integer array bills where bills[i] is the bill the ith customer pays, return true if you can provide every customer with the correct change, or false otherwise.

The change needed is $10 and $20, and the change used is $5. As you can see from this, $5 is the best, giving change for both $10 and $20, but $10 can only give change for $20.

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

Question 2

406. Queue Reconstruction by Height

You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [hi, ki] represents the ith person of height hi with exactly ki other people in front who have a height greater than or equal to hi.

Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [hj, kj] is the attributes of the jth person in the queue (queue[0] is the person at the front of the queue).

There are two dimensions, h and k, which would be lost if considered at the same time.

After sorting by height from largest to smallest:

• Local optimum: insertion is preferred according to the k of the people with high height. The people after the insertion operation satisfy the queue property

• Global optimal: all the insertion operations are done at last, and the whole queue satisfies the topic queue property.

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x: (-x[0], x[1]))
        que = []
        for p in people:
            que.insert(p[1], p)
        return que

Question 3

452. Minimum Number of Arrows to Burst Balloons

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.

Given the array points, return the minimum number of arrows that must be shot to burst all balloons.

A two-dimensional array is used to represent the widths of the balloons, and when there are balloons overlapping in width, an arrow can be shot through the overlapping balloons.

In order for the balloons to overlap, they can be sorted first.

If the balloons overlap, the interval before the minimum of the right boundary in the overlapping balloons must require a bow and arrow.

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