A clean java solution


  • 41
    D
    public class Solution {
        public List<Interval> merge(List<Interval> intervals) {
            Collections.sort(intervals, new Comparator<Interval>(){
                @Override
                public int compare(Interval obj0, Interval obj1) {
                    return obj0.start - obj1.start;
                }
            });
    
            List<Interval> ret = new ArrayList<>();
            Interval prev = null;
            for (Interval inter : intervals) {
                if (  prev==null || inter.start>prev.end ) {
                    ret.add(inter);
                    prev = inter;
                } else if (inter.end>prev.end) {
                    // Modify the element already in list
                    prev.end = inter.end;
                }
            }
            return ret;
        }
    }

  • 0
    W

    Thanks for the clean code!


  • 2
    K

    Concise java solution

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

  • 0
    D

    You use remove function, which will cost O(n) each time in worst case. That means, in your for loop, the time complexity is O(n^2).


  • 0

    @dianren I delete the useless elements in the end to achieve a O(n) solution without extra space

    public List<Interval> merge(List<Interval> intervals) {
            if(intervals.size()<2) return intervals;
            intervals.sort((Interval intervalA, Interval intervalB)->(intervalA.start - intervalB.start));
    	int index = 0; int remove = 0;
    	for(int i = 1; i<intervals.size(); i++){
    		if(intervals.get(index).end>=intervals.get(i).start){
    			intervals.get(index).end = Math.max(intervals.get(index).end,intervals.get(i).end); 
    			remove++;
    		}
    		else{
    			index++;
    			intervals.get(index).start = intervals.get(i).start;
    			intervals.get(index).end = intervals.get(i).end;
    		}
    	}
    	while(remove-->0) intervals.remove(intervals.size()-1);
    	return intervals;
    }

Log in to reply
 

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