452. Minimum Number of Arrows to Burst Balloons

Intuition

It’s told that a balloon with xStart and xEnd gets shot from x if xStart <= x <= xEnd.
The arrow will continue through its path and if the balloons are on its past, then surely the balloon will burst.
Now here we actually need to find how many balloons are present in an overlapping xStart and xEnd.

So thus it boils down to the number of nonoverlapping intervals such that all the balloons which are in the interval which are also overlapped by some other intervals can be shot from a position x and with just 1 arrow all those balloons can be burst.

Approach

Blindly going with the approach of finding the count of nonoverlapping intervals.

• Sort the intervals based on the end time. (Can also be done using start time but then we have to do it in reverse).

• Point to an end node, let's say currentEnd=Long.MIN_VALUE.(Here long is used as in the constraints -2^31 <= xstart < xend <= 23^1 - 1. So if we use int, we will get wrong answer for the last test case).

• Traverse through the array and see if the starting point > the currentEnd, if yes then it's not overlapping and till that interval, we can shoot all the balloons with one arrow. Just increment the arrow count and set currentEnd = nextEnd.

Complexity

• Time complexity:
  We are sorting the array + traversing through the array.
  So time complexity will be O(nlogn) + O(n) where n = length of array.

• Space complexity:
  No extra space is used even though the sorting might use some space.
  But we can say space complexity is O(1).

Code

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points == null || points.length == 0) {
            return 0;
        }
        int length = points.length;
        int minimumNumberOfBalloons = 0;
        Arrays.sort(points, (p1, p2) -> Integer.compare(p1[1], p2[1]));
        long currentEnd = Long.MIN_VALUE;
        for (int [] point : points) {
            int nextStart = point[0];
            int nextEnd = point[1];
            if (nextStart > currentEnd) {
                currentEnd = nextEnd;
                minimumNumberOfBalloons++;
            }
        }
        return minimumNumberOfBalloons;
    }
}

Please feel free to suggest other approaches or mistake in any of my understanding.
Thanks