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.
Example 1:
Input: points = [[10,16],[2,8],[1,6],[7,12]] Output: 2 Explanation: The balloons can be burst by 2 arrows: - Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6]. - Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12].
思路：最少多少剑射穿气球。
先对气球按照一边的大小进行排序。若按照左边界，那么当前气球的左边界如果大于之前累积的气球的右边界，就必须得加一支箭才可以射穿当前气球了。
以这个思路，更详细分析就是要记录当前累计气球的交集，也就是在哪个范围内当前箭可射穿当前累计的所有气球。若气球1是[2,5], 气球2是[3,6], 那么这个交集的区间是[3,5], 左边界是3，右边界是5，如果新来的气球的左边界大于了5，那么就无法用同一支箭射穿了。这种情况下，写法上可以选择更新原气球数组，每次都把当前气球i的左右边界更新为当前箭可射穿的左右边界，如果下一个气球i依然可以被同一支箭射穿，那就继续更新下一个气球的右边界，否则就不更新了，算是新一支箭的左右边界。另一种不更新原数组的写法就是记录当前箭的左右边界。
不过注意了，更简化的算法是只更新右边界就可以了，左边界的更新是冗余的。因为排过序，新的左边界肯定大于旧的左边界，所以只要新的左边界小于旧的右边界，左边界就一定是落在原来区间的，反之则不然。
另外要注意的一点是xstart <= x <= xend就可以射穿，这里是闭区间，所以判断是否需要一支新箭时，取的是右边界大于之前的左边界时才要换，而不是大于等于。
还有写法上如果涉及i-1，for循环序号就要注意从1开始。那么序号为0的情况就要特别处理，或可考虑作为初始化。
class Solution(object):
def findMinArrowShots(self, points):
"""
:type points: List[List[int]]
:rtype: 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
"""
points.sort(key = lambda x:x[0])
sl, sr = points[0][0], points[0][1] # use sl and sr to record the left and right boundary of the current interval separately.
count = 1
for i in points:
if i[0] > sr: # if the left boundary of this balloons is out of current interval, we need a now arrow.
count += 1
sl, sr = i[0], i[1] #注意，不仅仅是右边界要更新，左边界也是要更新的！！
else:
sl = max(sl, i[0]) # 不要搞错了min和max，这里要的是区间的交集不是并集
sr = min(sr, i[1])
return count
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).
Example 1:
Input: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] Output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] Explanation: Person 0 has height 5 with no other people taller or the same height in front. Person 1 has height 7 with no other people taller or the same height in front. Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1. Person 3 has height 6 with one person taller or the same height in front, which is person 1. Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3. Person 5 has height 7 with one person taller or the same height in front, which is person 1. Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is the reconstructed queue.
思路：根据身高重建队列。有两重排序标准，第一是身高h从高到低，第二是要求前面有k个比自己高的。先按照第一重标准排序，并且这个时候对于相同的h，k小的在前面（即使在最终的排序结果中，k小的也应该在前面）。再按照第二重标准来，第一重排序中靠前的具有优先排序的资格。因为本身身低的并不继续影响前面身高高的k值了。
写法上要注意 people.sort(key=lambda x:(-x[0], x[1])) ，表示先按照x[0] 从大到小排序（通过取负数得到），x[0]相同的情况下，再考虑x[1]由小到大排序。
另外，插入的写法是 que.insert(i[1],i) 。一开始我错误地写成了que[i[1]] = i ... 这样意思就完全错了。。。
以及，一开始做这道题时，并没考虑h相同k不同的情况。这点也应该考虑周全了。
class Solution(object):
def reconstructQueue(self, people):
"""
:type people: List[List[int]]
:rtype: List[List[int]]
"""
# 先按照h维度的身高顺序从高到低排序。确定第一个维度
# lambda返回的是一个元组：当-x[0](维度h）相同时，再根据x[1]（维度k）从小到大排序
people.sort(key=lambda x:(-x[0], x[1]))
que = []
# 根据每个元素的第二个维度k，贪心算法，进行插入
# people已经排序过了：同一高度时k值小的排前面。
for i in people:
que.insert(i[1],i)
return que860. 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.
Example 1:
Input: bills = [5,5,5,10,20] Output: true Explanation: From the first 3 customers, we collect three $5 bills in order. From the fourth customer, we collect a $10 bill and give back a $5. From the fifth customer, we give a $10 bill and a $5 bill. Since all customers got correct change, we output true.
思路：这道题乍一看有点复杂，列出所有可能的情况后发现其实很简单。
只需要维护三种金额的数量，5，10和20。
有如下三种情况：
- 情况一：账单是5，直接收下。
- 情况二：账单是10，消耗一个5，增加一个10
- 情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5
因为5可以被用来解决2、3两种情况，而10只可以解决3。所以优先花掉10，如果没有10的话再去找5救火。
class Solution(object):
def lemonadeChange(self, bills):
"""
:type bills: List[int]
:rtype: bool
"""
five = 0
ten = 0
twenty = 0
for bill in bills:
# 情况一：收到5美元
if bill == 5:
five += 1
# 情况二：收到10美元
if bill == 10:
if five <= 0:
return False
ten += 1
five -= 1
# 情况三：收到20美元
if bill == 20:
# 先尝试使用10美元和5美元找零
if five > 0 and ten > 0:
five -= 1
ten -= 1
#twenty += 1
# 如果无法使用10美元找零，则尝试使用三张5美元找零
elif five >= 3:
five -= 3
#twenty += 1
else:
return False
return True
