my java solution,using labeling method,easy to understand


  • 0
    X

    public List<Interval> merge(List<Interval> intervals) {

        List<Interval> res=new ArrayList<Interval>();
        int n=intervals.size();
        if(intervals.size()<=1){
        	return intervals;
        }
        int min=intervals.get(0).start;
    	int max=intervals.get(0).end;
        for(int i=0;i<n;i++){
        	Interval temp=intervals.get(i);
        	min=temp.start<min?temp.start:min;
        	max=temp.end>max?temp.end:max;
        }
        boolean[] flag=new boolean[2*max+1];
        for(int i=2*min;i<=2*max;i++){
        	flag[i]=false;
        }
    	for(int i=0;i<n;i++){
    		Interval temp=intervals.get(i);
    		for(int j=2*temp.start;j<=2*temp.end;j++){
    			flag[j]=true;
    		}
    	}
    	int i=2*min;
        while(i<=2*max){
        	int s=i/2;
        	while(i<=2*max && flag[i]){
        		i++;
        	}
        	int e=(i-1)/2;
        	res.add(new Interval(s,e)); 
        	while(i<=2*max && !flag[i]){
        		i++;
        	}
        }
    	return res;
    }

Log in to reply
 

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