Java solution using PriorityQueue


  • 0
    M
    public class Solution {
        public List<Interval> merge(List<Interval> intervals) {
            List<Interval> li = new LinkedList<Interval>();
            if(intervals == null || intervals.size()==0){
                return li;
            }
            Queue<Interval> q = new PriorityQueue<Interval>(new Comparator<Interval>(){
               public int compare(Interval i1, Interval i2){
                   if(i1.start == i2.start){
                       return i1.end-i2.end;
                   }
                   return i1.start-i2.start;
               }
            });
            for(Interval interval : intervals){
                q.offer(interval);
            }
            Interval n = q.remove();
            while(!q.isEmpty()){
                if(n.end < q.peek().start){
                    li.add(n);
                    n=q.remove();
                }else{
                    while(!q.isEmpty() && n.end>=q.peek().start){
                        if(n.end<q.peek().end){
                            n.end=q.peek().end;
                        }
                        q.remove();
                    }
                    
                }
            }
            li.add(n);
            return li;
            
        }
    }
    

Log in to reply
 

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