Java solution based on priority queue


  • 0
    J
        public List<Interval> merge(List<Interval> intervals) {
            if (intervals == null || intervals.size() <= 1) return intervals;
            PriorityQueue<Interval> queue = new PriorityQueue<>(new Comparator<Interval>() {
                public int compare(Interval v1, Interval v2) { 
                    return v1.start - v2.start;
                }
            });
            List<Interval> result = new ArrayList<>();
            for (Interval v : intervals) queue.offer(v);
            while (!queue.isEmpty()) {
                Interval v = queue.poll();
                boolean toAdd = true;
                if (!queue.isEmpty()) {
                    Interval v2 = queue.peek();
                    if (v2.start <= v.end) {
                        v2 = queue.poll();
                        v2.start = v.start;
                        v2.end = v2.end > v.end ? v2.end : v.end;
                        queue.offer(v2);
                        toAdd = false;
                    }
                } 
                if (toAdd) result.add(v);
            }
            return result;
        }
    

Log in to reply
 

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