Beats 99% java. Simple with explanation.


  • 1
    M

    So the trick here is to multiply number by 10 and identify start and end with a plus one.
    This way, I know which element in the array is "start" and which is "end". The rest of the
    code is simply iterate through a sorted array and find a start bound and an end bound.

    public class Solution {
        public List<Interval> merge(List<Interval> intervals) {
        	if(intervals.size()==0) return new ArrayList<Interval>();
        	int[] intArr=new int[2*intervals.size()];
        	int scount=0,start=0;
            List<Interval> result=new ArrayList<Interval>();
        	for(int i=0;i<2*intervals.size();i+=2){
        	    intArr[i]=intervals.get(i/2).start*10;
        	    intArr[i+1]=intervals.get(i/2).end*10+1;
        	}
        	Arrays.sort(intArr);
        	for(int i=0;i<intArr.length;i++){
        	    if(scount==0){//initialization 
        	       start=intArr[i]/10;
        	       scount++;
        	       continue;
        	    }
        	    if(intArr[i]%10!=0){
        	        scount--;
        	        if(scount==0) result.add(new Interval(start,(intArr[i]-1)/10));//if start bound count is equal to end bound count
        	    }
        	    else{
        	        scount++;//find more than one start bound so need to find equal number end bound count
        	    }
        	}
        	return result;
        }
    }
    

Log in to reply
 

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