A simple Java solution


  • 151
    B

    The idea is to sort the intervals by their starting points. Then, we take the first interval and compare its end with the next intervals starts. As long as they overlap, we update the end to be the max end of the overlapping intervals. Once we find a non overlapping interval, we can add the previous "extended" interval and start over.

    Sorting takes O(n log(n)) and merging the intervals takes O(n). So, the resulting algorithm takes O(n log(n)).

    I used an a lambda comparator (Java 8) and a for-each loop to try to keep the code clean and simple.

    public List<Interval> merge(List<Interval> intervals) {
        if (intervals.size() <= 1)
            return intervals;
        
        // Sort by ascending starting point using an anonymous Comparator
        intervals.sort((i1, i2) -> Integer.compare(i1.start, i2.start));
        
        List<Interval> result = new LinkedList<Interval>();
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        
        for (Interval interval : intervals) {
            if (interval.start <= end) // Overlapping intervals, move the end if needed
                end = Math.max(end, interval.end);
            else {                     // Disjoint intervals, add the previous one and reset bounds
                result.add(new Interval(start, end));
                start = interval.start;
                end = interval.end;
            }
        }
        
        // Add the last interval
        result.add(new Interval(start, end));
        return result;
    }
    

    EDIT: Updated with Java 8 lambda comparator.


  • 2
    L

    Is there really a function called Integer.compare(a,b)?


  • 1
    L

    Alright, I was looking at Java 6. There is Integer.compare() since Java 1.7


  • 0
    Z
    This post is deleted!

  • 1
    B

    remove is an O(n) operation. So, in the worst case, you would end up with a quadratic algorithm instead of linearithmic.

    And if the list is a LinkedList, get(i) and get(i + 1) can also take linear time (not 100% sure about this one but it seems very plausible), making this implementation quite inefficient (quadratic again).

    The for-each loop, on the other hand, takes linear time to access all elements whatever list is used (ArrayList or LinkedList).


  • 19
    S

    Mine is similar, but one difference is I use the iterator to iterate through the original list and then directly modify it, So the final results are already in the "intervals" list.

    	public List<Interval> merge(List<Interval> intervals) {
    	if (intervals == null || intervals.isEmpty())
    		return intervals;
    	Collections.sort(intervals, new Comparator<Interval>() {
    		public int compare(Interval i1, Interval i2) {
    			if (i1.start != i2.start) {
    				return i1.start - i2.start;
    			}
    			return i1.end - i2.end;
    		}
    	});
    	ListIterator<Interval> it = intervals.listIterator();
    	Interval cur = it.next();
    	while (it.hasNext()) {
    		Interval next = it.next();
    		if (cur.end < next.start) {
    			cur = next;
    			continue;
    		} else {
    			cur.end = Math.max(cur.end, next.end);
    			it.remove();
    		}
    	}
    	return intervals;
    }

  • 1
    B

    I see just a little problem with this code. It works fine with a LinkedList but with an ArrayList, remove() takes linear time. In the worst case, that'd make the algorithmm quadratic. So, that makes the algorithm dependent on the type of list used.


  • 0
    T

    Thank you! The following is c++ version:

    vector<Interval> merge(vector<Interval>& intervals) {
            vector<Interval> res;
            if(intervals.empty()) return res;
    		sort(intervals.begin(), intervals.end(), 
    		    [](const Interval &a, const Interval &b){ 
    			    return a.start < b.start;
    			}
    		);
    		int curstart = intervals[0].start;
    		int curend = intervals[0].end;
    		for (int i = 1; i < intervals.size(); ++i)
    		{
    		    if(intervals[i].start > curend){
    		        res.emplace_back(curstart, curend);
    		        curstart = intervals[i].start;
    		        curend = intervals[i].end;
    		    }else if(intervals[i].end > curend){
    		        curend = intervals[i].end;
    		    }
    		}
    		res.emplace_back(curstart, curend);
    		return res;
        }

  • 8
    K

    Similar idea.

    public class Solution {
        public List<Interval> merge(List<Interval> intervals) {
            List<Interval> result = new LinkedList<Interval>();
            Collections.sort(intervals,new Comparator<Interval>() {
               public int compare(Interval i1, Interval i2) {
                    return i1.start - i2.start;       
               } 
            });
            
            int i = 0;
            while(i < intervals.size()-1) {
                Interval current = intervals.get(i);
                Interval next = intervals.get(i+1);
                if(next.start <= current.end) {
                    int max = Math.max(next.end, current.end);
                    current.end = max;
                    intervals.remove(i+1);
                } else {
                    i++;
                }
            }
            return intervals;
        }
    }

  • 0

    It's OK to just return a.start - b.start;


  • 6
    J

    Very clear and nice solution! I changed the sorting part to lambda style to save some typing.

    intervals.sort((i1, i2) -> Integer.compare(i1.start, i2.start));
    

  • 0
    S
    This post is deleted!

  • 0
    J

    Space complexity is less, however, running time is more.


  • 0
    S

    Clean and concise, upvote!


  • 0

    Very similar! It seems like there're many ways for merging part. Perhaps due to the lambda, mine runs very slow...

        public List<Interval> merge(List<Interval> intervals) {
            intervals.sort((i1, i2) -> (Integer.compare(i1.start, i2.start)));
            List<Interval> result = new ArrayList<>();
            for (Interval interval : intervals) {
                if (!result.isEmpty() && result.get(result.size() - 1).end >= interval.start) {
                    Interval prev = result.get(result.size() - 1);
                    prev.start = Math.min(prev.start, interval.start);
                    prev.end = Math.max(prev.end, interval.end);
                } else {
                    result.add(interval);
                }
            }
            return result;
        }
    

    And here is another version using for-each and sparing "prev" by storing and comparing to last element in ret.

        public List<Interval> merge(List<Interval> ints) {
            if (ints.isEmpty()) return new ArrayList<>();
            ints.sort(Comparator.comparingInt(i -> i.start)); // must sort by start, eg.[2,3],[4,5],[1,10]
            LinkedList<Interval> ret = new LinkedList<>();
            
            for (Interval in : ints) {
                if (!ret.isEmpty() && in.start <= ret.getLast().end) {
                    ret.getLast().end = Math.max(ret.getLast().end, in.end); // no need to revise start
                } else 
                    ret.add(new Interval(in.start, in.end));
            }
            return ret;
        }
    

  • 1
    K

    @cdai I don't think this line is actually necessary :
    prev.start = Math.min(prev.start, interval.start);
    because you already sorted intervals by their start values .


  • 4

    Share my Java solution:

    public List<Interval> merge(List<Interval> intervals) {
        List<Interval> r = new ArrayList();
        if(intervals == null || intervals.size() == 0) return r;
        intervals.sort((i1, i2) -> Integer.compare(i1.start, i2.start));  
        
        Interval f = intervals.get(0);
        int s = f.start;
        int e = f.end;
    
        
        for(Interval i : intervals){
            if(i.start <= e){
                e = Math.max(i.end,e);
            }else {
                r.add(new Interval(s,e));
                s = i.start;
                e = i.end;
            }
        }
        
        r.add(new Interval(s,e));
        return r;
    }

  • 5
    L

    My concise Java code using Stack:

         public List<Interval> merge(List<Interval> intervals) {
            Stack<Interval> stack = new Stack();
            Collections.sort(intervals, (a,b) -> a.start - b.start);
            for(Interval it: intervals){
                if(stack.isEmpty() || it.start > stack.peek().end) stack.push(it);
                else{
                    stack.peek().end = Math.max(it.end, stack.peek().end);
                }
            }
            return new ArrayList(stack);
        }
    

  • 0

    @kira4 Thanks for pointing out!


  • 0
    Y

    Thanks for the updated java 8 version. That is so concise and understandable!


Log in to reply
 

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