Java code without sorting, time O(n)+ space O(n) (n=max(end)-min(start)), beat 99.01%


  • -1
    F
    public class Solution {
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals==null) return null;
        for(int i=0; i<intervals.size(); i++) {
            max = Math.max(max, intervals.get(i).end);
            min = Math.min(min, intervals.get(i).start);
        }
        int length = (max-min+1)*2;
        // Boolean hash to show the interval which are covered
        boolean[] cover = new boolean[length];
        for(int j=0; j<length; j++){
            cover[j] = false;
        }
        // Start cover interval
        for(int i=0; i<intervals.size(); i++) {
            int start = num2index(intervals.get(i).start);
            int end = num2index(intervals.get(i).end);
            for(int j= start; j<=end; j++){
                cover[j] = true;
            }
        }
        
        // Check cover interval
        List<Interval> result = new ArrayList<Interval>();
        boolean indicator_interval = false;
        int tmpStart=0, tmpEnd=0;
        for(int j=0; j<length; j++){
            if(cover[j] && !indicator_interval) {
                indicator_interval = true;
                tmpStart=index2num(j);
            }
            if(!cover[j] && indicator_interval){
                indicator_interval = false;
                tmpEnd = index2num(j-1);
                result.add(new Interval(tmpStart, tmpEnd));
            }
        }
        return result;
    }
    
    public int num2index(int num) {
        return 2*(num-min);
    }
    public int index2num(int index) {
        return index/2+min;
    }
    }

  • 0
    S

    why is multiplied by 2 there ?


  • 0
    F

    In order to handle the case like [5,9] [10,14]


  • 0
    Y

    I also came up with this idea but abandoned. Think about the test case [1,1000001],[2,3], this 'counting' solution cannot be more efficient than using a sorting-based solution. Actually sorting solutions have O(nlgn) where n is number of intervals, while in this solution, its n can be infinity.


  • 0
    F

    You are right. The solution efficiency is really depends on the test cases. In my point, this kind of method is more straight forwards than sorting.


Log in to reply
 

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