Easy to understand Java solution using Deque

  • 0

    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);
            Interval i1, i2;
            while(!queue.isEmpty()) {
                i1 = queue.pollFirst();
                if(queue.isEmpty()) {
                }else {
                    i2 = queue.pollFirst();
                    if(i2.start <= i1.end) { // merge
                        Interval i = new Interval(i1.start, i2.end >= i1.end ? i2.end : i1.end);
                    }else { // not merge
            return result;

Log in to reply

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