There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart &lt;= x &lt;= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.

Given the array points, return the minimum number of arrows that must be shot to burst all balloons.

&nbsp;
Example 1:

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6].
- Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12].


Example 2:

Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4
Explanation: One arrow needs to be shot for each balloon for a total of 4 arrows.


Example 3:

Input: points = [[1,2],[2,3],[3,4],[4,5]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 2, bursting the balloons [1,2] and [2,3].
- Shoot an arrow at x = 4, bursting the balloons [3,4] and [4,5].


&nbsp;
Constraints:


	1 &lt;= points.length &lt;= 105
	points[i].length == 2
	-231 &lt;= xstart &lt; xend &lt;= 231 - 1


class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort()
        
        ans=[points[0]]
        for i in points[1:]:
            if(i[0]<=ans[-1][1]):
                ans[-1]=[ans[-1][0],min(ans[-1][1],i[1])]
            else:
                ans.append(i)
        return len(ans)
        
class Solution {
    public int findMinArrowShots(int[][] points) {
        
        int minNumArrows = 1;
        Arrays.sort(points, new Comparator<int[]>(){
            @Override
            public int compare(int[] i1, int[] i2)
            {
                if(i1[0] < i2[0])
                    return -1;
                else if (i1[0] > i2[0])
                    return 1;
                return 0;
            }
        });
            
        // This is where they will trip you up ( at the merge stage )
        // Wait ... do we actually have to merge here? The intervals have been sorted already
        // No you must merge
        // See if they can be merged
        // If mergeable - overwrite OR write into a new subintervals code ( new ArrayList ) 
        // Ok ... so first we compare (a1,a2) and then next step compare (a2,a3)
        // Now if (a1,a2) had an overlap -> why not make the next a2 = merged(a1,a2)? 
        // That would do a carry over effect then
        int n = points.length;
        int[] candid = new int[2];  // always first interval anyways
        candid[0] = points[0][0];
        candid[1] = points[0][1];
        for(int i = 1; i < n; i++)
        {
            // System.out.printf("Current set = (%d,%d)\n", candid[0], candid[1]);
            int[] next = points[i];
            if(hasOverlap(candid,next))
            {
                int[] merged = mergeInterval(candid,next);
                candid[0] = merged[0];
                candid[1] = merged[1];
            }
            else
            {
                candid[0] = next[0];
                candid[1] = next[1];                
                minNumArrows++;
            }
        }
         
        return minNumArrows;
    }
    
    public boolean hasOverlap(int[] i1, int[] i2)
    {
        boolean hasOverlap = false;
        if(i1[0] <= i2[0] && i2[0] <= i1[1])
            hasOverlap = true;
        if(i2[0] <= i1[0] && i1[0] <= i2[1])
            hasOverlap = true;
        return hasOverlap;
    }
    
    public int[] mergeInterval(int[] i1, int[] i2)
    {
        int[] merged = new int[2];
        merged[0] = Math.max(i1[0],i2[0]);
        merged[1] = Math.min(i1[1],i2[1]);
        return merged;
    }
}
class Solution {
public:
    static bool cmp(vector<int>&a,vector<int>&b)
    {
        return a[1]<b[1];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(),points.end(),cmp);
        //burst the first ballon at least
        int arrow=1;
        int end=points[0][1];
        for(int i=1;i<points.size();i++)
        {
            //start time of other interval is greater than current end time means we need one more arrow for bursting it
            if(points[i][0]>end)
            {
                arrow++;
                end=points[i][1];
            }
        }
        return arrow;
    }
};
var findMinArrowShots = function(points) {
    points.sort((a, b) => a[0] - b[0])

    let merged = [points[0]];

    let earliestEnd = points[0][1];

    for (let i = 1; i < points.length; i++) {
        let lastEnd = merged[merged.length - 1][1];
        let currStart = points[i][0];
        let currEnd = points[i][1];

        if (lastEnd >= currStart && currStart <= earliestEnd) {
            merged[merged.length - 1][1] = Math.max(lastEnd, currEnd)
            earliestEnd = Math.min(earliestEnd, points[i][1]);
        }
        else {
            merged.push(points[i])
            earliestEnd = points[i][1]
        }
    }

    return merged.length
};
Minimum Number of Arrows to Burst Balloons