Java Solution (26ms, beats 100%)


  • 0
    Q

    First using quick sort applying on the start of each point; then iterative from the beginning of the sorted array by calculating the end of the previous point (intersected points results in e.g. [1,4], [2,5] -> [2,4], end of previous: 4). An virtual point not intersecting the last one was added at the end of the points to fulfill the border condition.

    public int findMinArrowShots(int[][] points) {
            if (points == null || points.length == 0) {
    			return 0;
    		}
    		if (points.length == 1) {
    			return 1;
    		}
    		int length = points.length;
    		sortStart(points, 0, length - 1);
    		
    		int i = 0;
    		int count = 0;
    		int lastEnd = points[0][1];
    		int currentStart = 0;
    		int currentEnd = 0;
    					
    		while (i < length + 1) {
    			if (i < length) {
    				currentStart = points[i][0];
    				currentEnd = points[i][1];
    			} else {
    				currentStart = points[length - 1][1] + 1;
    				currentStart = points[length - 1][1] + 1;
    			}
    			if (lastEnd >= currentStart) {
    				lastEnd = (lastEnd > currentEnd) ? currentEnd : lastEnd;
    			} else {
    				if (i < length) {
    					lastEnd = points[i][1];
    				} 
    				count++;
    			}
    			i++;
    		}
    		
    		return count;
        }
        
        private void sortStart(int[][] points, int leftIndex, int rightIndex) {
    		int i = leftIndex;
    		int j = rightIndex;
    		int m = leftIndex + (rightIndex - leftIndex) / 2;
    		int mValue = points[m][0];
    		
    		if (i >= j) {
    			return;
    		}
    		
    		while (i < j) {
    			while (points[i][0] < mValue) {
    				i++;
    			}
    			while (points[j][0] > mValue) {
    				j--;
    			}
    			
    			if (i <= j) {
    				int tempStart = points[i][0];
    				points[i][0] = points[j][0];
    				points[j][0] = tempStart;
    				int tempEnd = points[i][1];
    				points[i][1] = points[j][1];
    				points[j][1] = tempEnd;
    				i++;
    				j--;
    			}
    		}
    		sortStart(points, leftIndex, j);
    		sortStart(points, i, rightIndex);
    	}

Log in to reply
 

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