use PQ to sort, easy java, beats 90%


  • 0
    N
    public class Solution {
        public List<Interval> merge(List<Interval> intervals) {
            List<Interval> res = new ArrayList<Interval>();
            if(intervals == null || intervals.size() == 0){
                return res;
            }
            
            /*
            * use PriorityQueue to sort the intervals
            */
            PriorityQueue<Interval> minPQ = new PriorityQueue<Interval>(intervals.size(), new Comparator<Interval>(){
                @Override
                public int compare(Interval a, Interval b){
                    return a.start - b.start;
                }
            });
            
            for(Interval i : intervals){
                minPQ.add(i);
            }
            
            Interval cur = minPQ.poll();
            
            while(!minPQ.isEmpty()){
                Interval next = minPQ.poll();
                if(cur.end >= next.start){
                    cur = new Interval(cur.start, Math.max(cur.end, next.end));
                    continue;
                }
                else{
                    res.add(new Interval(cur.start, cur.end));
                    cur = next;
                }
            }
            
            /*
            *to check the last interval
            */
            if(!res.contains(cur)){
                res.add(new Interval(cur.start, cur.end));
            }
            return res;
        }
    }
    

Log in to reply
 

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