A real O(NlogN) solution bases on Java


  • 0
    E

    My solution uses sort first, and uses divide and conquer to merge the Interval.

    The most popular solution for this problem is not real O(NlogN), because their remove method for merging will cause O(N2).

    The time complexity of my solution is real O(NlogN), but the disadvantage is that the space complexity is big. This is the disadvantage of divide and conquer and merger sort.

    public List<Interval> merge(List<Interval> intervals) {
    
        if (intervals.size()==0) return new ArrayList<Interval>();
    
       Collections.sort(intervals, new Comparator<Interval>() {
           @Override
           public int compare(Interval o1, Interval o2) {
               return o1.start-o2.start;
           }
       });
    
        List<Interval> result = this.divide(intervals);
    
        return result;
    
    }
    
    private List<Interval> divide(List<Interval> intervals) {
    
        if (intervals.size()==1)
            return intervals;
    
        int size = intervals.size()/2;
    
        List<Interval> left = new ArrayList<>();
        List<Interval> right = new ArrayList<>();
    
        for (int i = 0; i < size; i++){
            left.add(intervals.get(i));
        }
    
        for (int i = size; i < intervals.size(); i++){
            right.add(intervals.get(i));
        }
    
        left = this.divide(left);
        right = this.divide(right);
    
        List<Interval> result = new ArrayList<>();
    
        Interval leftEnd = left.remove(left.size()-1);
        int i = 0;
        for (; i < right.size(); i++){
            Interval rightTemp = right.get(i);
            if ( rightTemp.start<=leftEnd.end && rightTemp.end<=leftEnd.end ){
                continue;
            }
            else if ( rightTemp.start<=leftEnd.end && rightTemp.end>leftEnd.end ){
                leftEnd = new Interval(leftEnd.start, rightTemp.end);
                i++;
                break;
            }
            else{
                break;
            }
        }
    
        for (int j = 0; j < left.size(); j++){
            result.add(left.get(j));
        }
        result.add(leftEnd);
        for (int j = i; j < right.size(); j++){
            result.add(right.get(j));
        }
    
        return result;
    
    }

Log in to reply
 

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