Java O(n lg n) time, O(1) space solution -- sort array


  • 0
    D
    public class Solution {
        
        public class BalloonComparator implements Comparator<int[]> {
            
            public int compare(int[] point1, int[] point2) {
                if (point1[0] != point2[0]) {
                    return point1[0] - point2[0];
                }
                return point1[1] - point2[1];
            }
            
        }
        
        public int findMinArrowShots(int[][] points) {
            if (points.length < 2) return points.length;
            
            //we need to sort the points first by start time
            Arrays.sort(points, new BalloonComparator());
            
            //start count at 1, since we need at least 1
            int arrowCount = 1;
            for (int i = 1; i < points.length; i++) {
                if (points[i-1][1] >= points[i][0]) {
                    points[i][1] = Math.min(points[i-1][1], points[i][1]);
                } else {
                    arrowCount++;
                }
            }
            
            return arrowCount;
        }
    }
    

Log in to reply
 

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