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

就是求交集的数量【1，5】【2，6】【8，12】
输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆【10，16】【7，12】

  • 时间复杂度：O(n_log_n)，其中 n 是数组points 的长度。排序的时间复杂度为O(n_log_n)，对所有气球进行遍历并计算答案的时间复杂度为 O(n)，其在渐进意义下小于前者，因此可以忽略。

  • 空间复杂度：O(logn)，即为排序需要使用的栈空间。

    解题思路1

    和其他合并区间类的题目套路一样, 都是贪心思想, 先排序, 然后遍历检查是否满足合并区间的条件
    这里判断是否有交叉区间, 所以其实是计算已知区间的交集数量.
    这里以[[10,16],[2,8],[1,6],[7,12]] 为例子:

  • 先排序, 我是按区间开始位置排序, 排序后: [[1,6],[2,8],[7,12],[10,16]]

  • 遍历计算交叉区间(待发射箭头),
    1. 待发射箭头的区间range = [1, 6], 需要的箭数量 arrows = 1;
    2. 区间[2, 8], 和带发射区间[1, 6]有交集: 更新发射区域为它们的交集 range = [2, 6]
    3. 区间[7, 12], 和待发射区间[2, 6]没有任何交集, 说明需要增加一个新的发射区域, 新的待发射区域range = [7, 12]
    4. 区间[10,16], 和待发射区域[7, 12]有交集, 待发射区域更新为[10, 12]
  • 返回需要待发射区间的个数
    1. //也是比较后区间
    2. func findMinArrowShots(points [][]int) int {
    3.   sort.Slice(points, func(i, j int) bool {
    4.       return points[i][1] < points[j][1]
    5.   })
    6.   count := 0  // 弓箭数
    7.   i := 0      // 遍历的指针
    8.   for i < len(points) {
    9.       right := points[i][1] // 当前区间的右端
    10.       i++                   // 考察下一个区间
    11.       for i < len(points) && points[i][0] <= right { // 避免i越界
    12.           i++               // 只要重合，i就推进，继续寻求与下一个的重合
    13.       }
    14.       count++               // 给重合的团伙来一箭
    15.   }
    16.   return count
    17. }

解题思路2

用区间的尾部排序貌似效率会更好, 因为已经保证后面的区间右侧都是大于当前区间, 所以将发射点设置在右侧边界, 后面的区间只有左边界比它更靠左,则可以被一起处理掉
这里换个example: [[10,16],[2,5],[1,6],[7,12]] 为例子:

  • 先排序, 按区间结束位置排序, 排序后: [[2,5],[1, 6],[7,12],[10,16]]

  • 遍历计算交叉区间,

    1. 发射点初始化为pos = 5, 需要的箭数量 arrows = 1;
    2. 区间[1, 6], 1 是小于5的, 在点5射箭可以干掉这个区间
    3. 区间[7, 12], 在5的位置射箭无法打掉, 说明需要增加一个新的发射点, 新的待发射点pos = 12

    4. 区间[10,16], 10 < 12那么在12位置射箭可以干掉它

      //从右值开始比较； 排序 + 贪心 + 重叠区间
func findMinArrowShots(points [][]int) int {
if len(points) == 0 {
  return 0
}
sort.Slice(points, func(i, j int) bool { 
      return points[i][1] < points[j][1] 
  })

maxRight := points[0][1]
ans := 1

for _, p := range points {
  if p[0] > maxRight {
      maxRight = p[1]
      ans++
  }
}
return ans
}