C# O(nlogn) using sort


  • 0
    S
    
    public class Solution {
        public int FindMinArrowShots(int[,] points) {
            if (points.GetUpperBound(0) == -1){
                return 0;
            }
            int totalArrows = 0;
            List<Point> allPoints = new List<Point>(points.GetUpperBound(0) + 1);
            for (int i = 0; i <= points.GetUpperBound(0); i++){
                allPoints.Add(new Point(points[i,0], points[i,1]));
            }
            
            allPoints = allPoints.OrderBy(x => x.ending).ToList();
            
            Point currentPoint = allPoints[0];
            totalArrows++;
            
            for (int i = 1; i < allPoints.Count; i++){
                if (currentPoint.ending >= allPoints[i].starting && currentPoint.ending <= allPoints[i].ending){
                    continue;
                }
                
                currentPoint = allPoints[i];
                totalArrows++;
            }
            
            return totalArrows;
        }
    }
    
    public class Point{
        public int starting;
        public int ending;
        public Point(int s, int e){
            starting = s;
            ending = e;
        }
    }
    

Log in to reply
 

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