Java solution in linear time O(n)


  • 0
    D
    public List<Interval> merge(List<Interval> intervals) {
            if(intervals.size()==0){
                return new ArrayList<>();
            }
    
            int minStart = Integer.MAX_VALUE;
            int maxEnd = Integer.MIN_VALUE;
            List<Interval> intervalList = new ArrayList<>();
    
            for(Interval interval: intervals) {
    
                minStart = Math.min(minStart, interval.start);
    
                maxEnd = Math.max(maxEnd, interval.end);
            }
            int[] arr = new int[maxEnd+2];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = 0;
            }
            int unique = 0;
            for(Interval interval: intervals){
                int start = interval.start;
                int end = interval.end;
                if(arr[start]==0 && arr[end]==0){
                    unique++;
                    while(start<=end){
                        arr[start++] = unique;
                    }
                } else if(arr[start]==0 && arr[end]!=0){
                    int index = start;
                    while(index<=end){
                        arr[index++] = arr[end];
                    }
                } else if(arr[end]==0 && arr[start]!=0){
                    int index = end;
                    while(index>=start){
                        arr[index--] = arr[start];
                    }
                } else {
                    int index = start;
                    int indexEnd = end;
                    while (arr[indexEnd]==arr[indexEnd+1]){
                        ++indexEnd;
                    }
                    while(index<=indexEnd){
                        arr[index++] = arr[start];
                    }
                }
            }
            /*for (int i = minStart; i <=maxEnd ; i++) {
                System.out.println(i + " : " +arr[i]);
            }*/
            int newStart = minStart;
            for (int i = minStart; i<=maxEnd; i++) {
                if(arr[i]!=arr[i+1]){
                    if(arr[newStart]!=0 && arr[i]!=0){
                        intervalList.add(new Interval(newStart, i));
                    }
                    newStart = i+1;
                }
            }
            return intervalList;
        }
    

Log in to reply
 

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