O(n log n) Using min heap, beats 63%


  • 0
    M
    class Solution {
        public List<Interval> merge(List<Interval> intervals) {
            List<Interval> list = new ArrayList<>();
            if(intervals == null || intervals.size() <= 1){
                return intervals;
            }
            Queue<Interval> queue = new PriorityQueue<>(100, new MyComparator());
            for(Interval i: intervals){
                queue.add(i);
            }
            
            Interval interval = queue.poll();
            int start = interval.start;
            int end = interval.end;
            while(!queue.isEmpty()){
                Interval temp = queue.poll();
                if(end >= temp.start){
                    end = Math.max(end, temp.end);
                }
                else{
                    list.add(new Interval(start, end));
                    start = temp.start;
                    end = temp.end;
                }
            }
            list.add(new Interval(start, end));
            return list;
        }
    }
    
    class MyComparator implements Comparator<Interval>{
        
        @Override
        public int compare(Interval one, Interval two){
            return one.start >= two.start ? 1: -1;
        }
    }
    

Log in to reply
 

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