Java scan x-axis solution, similar to meeting rooms


  • 0
    D
    public class Solution {
        public int findMinArrowShots(int[][] points) {
            if (points == null || points.length == 0) {
                return 0;
            }
            int n = points.length;
            Endpoint[] endpoints = new Endpoint[2 * n];
            for (int i = 0; i < n; i++) {
                endpoints[2 * i] = new Endpoint(i, points[i][0], true);
                endpoints[2 * i + 1] = new Endpoint(i, points[i][1], false);
            }
            Arrays.sort(endpoints, new Comparator<Endpoint>() {
                @Override
                public int compare(Endpoint e1, Endpoint e2) {
                    return e1.coordinate == e2.coordinate ? (e1.start ? -1 : 1) 
                            : e1.coordinate - e2.coordinate;
                }
            });
            Set<Integer> seenIds = new HashSet<>();
            Set<Integer> burstIds = new HashSet<>();
            int arrows = 0;
            for (int i = 0; i < 2 * n; i++) {
                Endpoint endpoint = endpoints[i];
                if (burstIds.contains(endpoint.id)) {
                    continue;
                }
                if (endpoint.start) {
                    seenIds.add(endpoint.id);
                } else {
                    arrows++;
                    burstIds.addAll(seenIds);
                    seenIds.clear();
                }
            }
            return arrows;
        }
        
        class Endpoint {
            int id;
            int coordinate;
            boolean start;
            Endpoint(int id, int coordinate, boolean start) {
                this.id = id;
                this.coordinate = coordinate;
                this.start = start;
            }
        }
    }
    

Log in to reply
 

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