Problem of The Day: Minimum Number of Arrows to Burst Balloons

Problem Statement

leetcode problem link

My Solution [Accepted]

public class Solution {
    public int FindMinArrowShots(int[][] points) {
        Array.Sort(points, (a, b) => {
            return a[0].CompareTo(b[0]);
        });

        int res = points.Count();
        int overlap_intervals = 0;
        int prev_end = int.MinValue;
        int i = 0; // Track iteration index to skip first interval processing

        foreach(int[] point in points) {
            int start = point[0];
            int end = point[1];
            if (i > 0 && prev_end >= start) { // Skip first interval; remove int.MinValue check
                overlap_intervals += 1;
                prev_end = Math.Min(prev_end, end);
            } else {
                prev_end = end;
            }
            i++; // Increment index
        }
        if (overlap_intervals == 0) {
            return res;
        }

        return res - overlap_intervals;
    }
}

Editorial

Approach 1: Greedy

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if not points:
            return 0

        # sort by x_end
        points.sort(key = lambda x : x[1])

        arrows = 1
        first_end = points[0][1]
        for x_start, x_end in points:
            # if the current balloon starts after the end of another one,
            # one needs one more arrow
            if first_end < x_start:
                arrows += 1
                first_end = x_end

        return arrows