Java Solution on Priority Solution


  • 1
    S
    public class Solution {
        public List<Interval> merge(List<Interval> intervals) {
            List<Interval> res = new LinkedList<Interval>();
            if(intervals==null||intervals.size()==0) return res;
            PriorityQueue<Interval> queue = new PriorityQueue<Interval>(new Comparator<Interval>(){
                public int compare(Interval o1, Interval o2){
                    return o1.end-o2.end;
                }
            });
            Interval[] arr = new Interval[intervals.size()];
            Object[] arrInterval = intervals.toArray();
            for(int i=0; i<intervals.size(); i++){
                arr[i] = (Interval)arrInterval[i];
            }
            Arrays.sort(arr, new Comparator<Interval>(){
                public int compare(Interval o1, Interval o2){
                    return o1.start-o2.start;
                }
            });
            queue.offer(arr[0]);
            for(int i=1; i<intervals.size(); i++){
                Interval curr = queue.poll();
                if(curr.end>=arr[i].start){
                    curr.end = curr.end>arr[i].end?curr.end:arr[i].end;
                    queue.offer(curr);
                }else{
                    queue.offer(arr[i]);
                    res.add(curr);
                }
            }
            Iterator itr = queue.iterator();
            while(itr.hasNext()){
                res.add((Interval)itr.next());
            }
            return res;
        }
    }

  • 0
    P

    You can also skip the sorting and put distinct points marked start/end in the queue.

    public class Solution {

    class Point implements Comparable<Point> {
        boolean start;
        int value;
        Point(int value, boolean start) {
            this.value = value;
            this.start = start;
        }
    
        @Override
        public int compareTo(Point that) {
            int cmp = Integer.compare(this.value, that.value);
            if (cmp == 0) {
                if (this.start && !that.start) {
                    cmp = -1;
                } else if (!this.start && that.start) {
                    cmp = 1;
                }
            }
            return cmp;
        }
    }
    
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals.size() <= 1) {
            return intervals;
        }
        PriorityQueue<Point> queue = new PriorityQueue<>();
        for (Interval i : intervals) {
            queue.add(new Point(i.start, true));
            queue.add(new Point(i.end, false));
        }
        
        List<Interval> result = new ArrayList<>();
        int startedCount = 0;
        int start = -1;
        while (!queue.isEmpty()) {
            Point p = queue.remove();
            if (p.start) {
                if (startedCount == 0) {
                    start = p.value;
                }
                startedCount++;
            } else {
                --startedCount;
                if (startedCount == 0) {
                    result.add(new Interval(start, p.value));
                    start = -1;
                }
            }
        }
        
        return result;
    }
    

    }


Log in to reply
 

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