Java ez understand solution


  • 0
    M

    we maintain an overlap interval, and update it in every iteration.

        public int findMinArrowShots(int[][] points) {
    		Arrays.sort(points, new Comparator<int[]>(){
    			@Override
    			public int compare(int[] a1, int[] a2) {
    				return a1[0] - a2[0] == 0 ? a1[1]-a2[1] : a1[0] - a2[0];
    			}
    		});
    		int numOfArrow = 0;
            
    		for (int i = 0; i < points.length; i++) {
    		    int upperlimit = points[i][1];
    		    int lowerlimit = points[i][0];
    		    numOfArrow++;
    			while (i + 1 < points.length && points[i+1][0] <= upperlimit) {//overlap occurs
    			    lowerlimit = points[i+1][0];
    			    if (points[i+1][1] < upperlimit) upperlimit = points[i+1][1];
    				i++;
    			}
    		}
    		return numOfArrow;
        }
    

Log in to reply
 

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