原题地址

0901.png

这题干也挺长的，但是说了个啥意思呢，我们给它扒拉扒拉，让它原形毕露。

如图

天空中飘着这么多五颜六色的气球，它们的y轴坐标忽略不计，只给出了x轴的起始坐标和结束坐标。现在我要在x轴沿着y轴方向射箭，问最少射出几根箭才能将气球全部扎破。0902.png

我们再抽象一下

问题变成了：穿过所有区间，至少需要几根线？
0903.png

这样的话题目的特性就很明显了，自然而然就想到了排序和贪心。

如果按照结束位置从小到大排序，那么问题就很简单了。

我们将一个气球用箭穿过的时候，从哪里穿才能使得这支箭多穿几个气球呢？

因为是按照结束位置从小到大排序的，所以从一个气球的结束位置穿过，能够保证在穿过本个气球的情况下，能够最多的穿后面的气球。

Python代码

  1. def findMinArrowShots(self, points: List[List[int]]) -> int:
  2.     n = len(points)
  3.     if n < 2:  # 特判
  4.         return n
  5.     points = sorted(points, key=lambda x: x[1])
  6.     # count计数， arrow记录当前这根箭的坐标，初始化为第一个气球的结束位置
  7.     count, arrow = 1, points[0][1]
  8.     for i in range(1, n):
  9.         # 如果这根箭能够穿过这个气球
  10.         if points[i][0] <= arrow and points[i][1] >= arrow:
  11.                 continue
  12.         # 如果这根箭不能穿过这个气球，那么拿一根新的箭
  13.         else:
  14.             arrow = points[i][1]
  15.             count += 1
  16.     return count

时间复杂度O(nlogn)

排序算法使用时间O(nlogn)

空间复杂度O(1)