O(N log N) solution based on sorting


  • 0
    G

    This problem actually asks us: how many intervals are left when you combine all possible intersections. Well, it get's a lot easier when we first sort the array by the starting points of the intervals. Due to sorting, we have a runtime complexity of O(N log N).

    1. Sort the array of intervals, starting with the smallest starting point.
    2. Store the current end of the interval.
    3. As long as the current end is bigger or equal the start of the interval, we don't need another arrow. Be careful here, we have to update the current end as it might happen that the end of this interval is smaller than our current one.
    4. If the start of the interval is bigger than our current end, we have to use a new arrow.

    Hope this helps you.

    public int findMinArrowShots(int[][] points) {
        if (points == null || points.length == 0) {
            return 0;
        }
            
        Arrays.sort(points, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return a[0] - b[0];
            }    
        });
            
        int arrowCount = 1;
        int currentEnd = points[0][1];
        for (int i = 1; i < points.length; i++) {
            if (currentEnd >= points[i][0]) {
                currentEnd = Math.min(points[i][1], currentEnd);
                continue;
            }
                
            currentEnd = points[i][1];
            arrowCount++;
        }
            
        return arrowCount;
    }
    

Log in to reply
 

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