Easy to understand Java solution using Comparator. Time: O(NlogN) Space:O(1)


  • 0
    D
    public List<Interval> merge(List<Interval> intervals) {
            //sort intervals in increasing order of 'start' , grouped by descreasing order of 'end'
    		Collections.sort(intervals, new Comparator<Interval>(){
    			public int compare(Interval a, Interval b){
    				int x =  a.start - b.start;
    				if(x==0)
    					return b.end-a.end;
    				else 
    					return x;
    			}
    		});
    		//indices that need to be removed from the list
    		List<Integer> removal = new ArrayList<Integer>();
    		
    		int n= intervals.size();
    		for(int i=0;i<n-1;){
    			Interval x = intervals.get(i);
    			int j=i+1;
    			for(;j<n;j++){
    				Interval y = intervals.get(j);
    				Integer s1 = x.start;
    				Integer e1 = x.end;
    				Integer s2 = y.start;
    				Integer e2 = y.end;
    				if(s2<=e1){
    					if(e2>e1){
    						x.end=e2;//if it is s2<=e1<e2// update the previous interval
    					}
    					removal.add(j);//mark jth interval(y) to be removed because, we have merged into the interval x
    				}else{
    					break;	//since e1>s2!
    				}
    			}//end of for j
    			
    			i=j;
    		}
    		for(int k=removal.size()-1;k>=0;k--){
    		    int r= removal.get(k);
    			intervals.remove(r);
    		}
    		return intervals;
        }
    

Log in to reply
 

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