452. Minimum Number of Arrows to Burst Balloons

Problem Statement

Pattern: Pattern Activity Selection Problem Related: 435. Non-Overlapping Intervals

---

Solution

    public int findMinArrowShots (int[][] points){
        Arrays.sort(points, Comparator.comparingInt(a -> a[1]));
        long prevEnd = Long.MIN_VALUE;
        int count = 0;
        for (int[] curr : points) {
            if(prevEnd < curr[0]){  // curr is overlapping
                count++;
                prevEnd = curr[1];
            }
        }
        return count;
    }

Notes

• sort intervals by their ends
• every time you come across a non-overlapping element increment count