Easy to understand Java Solution


  • 0
    F

    This problem is a sub-problem of finding intervals. We could solve this problem by sorting the input array properly.

    public class Solution {
        public int findMinArrowShots(int[][] points) {
            if (points == null || points.length == 0 || points[0].length == 0) return 0;
            // If Xstart is same, sort by based on its Xend (ascending)
            // Otherwise, sort by Xstart (ascending)
            Arrays.sort(points, new Comparator<int[]>() {
               @Override
               public int compare(int[] a, int[] b) {
                   if (a[0] == b[0]) return a[1] - b[1];
                   else return a[0] - b[0];
               }
            });
            
            int count = 1;
            int curLimit = points[0][1];
            for (int i = 1; i < points.length; i++) { 
                if (points[i][0] <= curLimit) {
                    // Check and update the current Xend
                    curLimit = Math.min(curLimit, points[i][1]);
                } else {
                    count++;
                    curLimit = points[i][1];
                }
            }
            return count;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.