Easy to understand Java solution using Deque


  • 0
    C

    First sort the list of intervals by each element's start value, time is O(nlogn). Then use a deque to keep trying to merge the top two elements, time is O(n) because each time the deque size will decrease by one.

    public class Solution {
        public List<Interval> merge(List<Interval> intervals) {
            List<Interval> result = new LinkedList<>();
            
            if(intervals == null || intervals.size() == 0)
                return result;
                        
            Deque<Interval> queue = new ArrayDeque<>();
            
            Collections.sort(intervals, (a, b) -> a.start - b.start);
            queue.addAll(intervals);
            Interval i1, i2;
            
            while(!queue.isEmpty()) {
                i1 = queue.pollFirst();
                if(queue.isEmpty()) {
                    result.add(i1);
                }else {
                    i2 = queue.pollFirst();
                    if(i2.start <= i1.end) { // merge
                        Interval i = new Interval(i1.start, i2.end >= i1.end ? i2.end : i1.end);
                        queue.offerFirst(i);
                    }else { // not merge
                        result.add(i1);
                        queue.offerFirst(i2);                   
                    }
                }
            }               
            return result;
        }
    }
    

Log in to reply
 

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