---
# System prepended metadata

title: 0452. Minimum Number of Arrows to Burst Balloons
tags: [Leetcode, Merge Interval, Medium]

---

# 0452. Minimum Number of Arrows to Burst Balloons
###### tags: `Leetcode` `Medium` `Merge Interval`
Link: https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/
## 思路 $O(NlogN)$ $O(1)$
首先按照start排序，排序的时候注意不能像line 6那样写```return a[0]-b[0]```，因为测资里面有$[[-2147483646,-2147483645],[2147483646,2147483647]]$，相减会出现overflow，所以需要改成```return Integer.compare(a[0],b[0]);```
在merge interval的时候一直记录当下最小的end，当来了新的[start，end] pair，拿start和最小的end比，如果比最小的end小就可以合并，否则不行～
## Code
```java=
class Solution {
    public int findMinArrowShots(int[][] points) {
        int ans = points.length;
        Arrays.sort(points, new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                // return a[0]-b[0];
                return Integer.compare(a[0],b[0]);
            }
        });
        int idx = 0;
        while(idx<points.length){
            int curr = points[idx++][1];
            while(idx<points.length && curr>=points[idx][0]){
                curr = Math.min(curr, points[idx][1]);
                ans--;
                idx++;
            }
        }
        return ans;
    }
}
```