[LeetCode] Minimum Number of Arrows to Burst Balloons

Problem: There are some spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it's horizontal, y-coordinates don't matter, and hence the x-coordinates of start and end of the diameter suffice. The start is always smaller than the end.

An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with xstart and xend bursts by an arrow shot at x if xstart ≤ x ≤ xend. There is no limit to the number of arrows that can be shot. An arrow once shot keeps traveling up infinitely.

Given an array points where points[i] = [xstart, xend], return the minimum number of arrows that must be shot to burst all balloons.

Example:

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).

Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4

Input: points = [[1,2],[2,3],[3,4],[4,5]]
Output: 2

Input: points = [[1,2]]
Output: 1

Input: points = [[2,3],[2,3]]
Output: 1

Approach: We can use sorting here. We sort the points based on the xend. Once we sort the array, we can follow the below steps:

• x = points[0][1]
• result = 0
• FOR i = 0 to n
• IF x < points[i][0]
• result = result + 1
• x = points[i][1]

Implementation in C#:

    public int FindMinArrowShots(int[][] points)

    {

        int length = points?.Length ?? 0;

        if (length <= 1)

        {

            return length;

        }

        Array.Sort(points, (p1, p2) => {

            return p1[1].CompareTo(p2[1]);

        });

        int count = 1;

        int compareIndex = 0;

        for (int i = 1; i < length; ++i)

        {

            if (points[compareIndex][1] < points[i][0])

            {

                ++count;

                compareIndex = i;

            }

        }

        return count;

    }

Complexity: O(nlogn)