My solution beats 93% Java. Sort & BinarySearch


  • 0
    B

    My solution beats 90%. Maintain two arrays storing merged intervals start and end separately. Use binarySearch to update them.

    public List<Interval> merge(List<Interval> intervals) {
        //if (intervals.size()==0) return new ArrayList<Interval>();
        intervals.sort(new Comparator<Interval>(){
            public int compare(Interval a, Interval b) {
                return a.start - b.start;
            }
        });
        int[] recordEnd = new int[intervals.size()];
        int[] recordStart = new int[intervals.size()];
        int len = 0;
        for (Interval interval:intervals) {
            int index = binarySearch(recordEnd, 0, len-1, interval.start);
            if (index==len) {
                len++;
                recordStart[index] = interval.start;
                recordEnd[index] = interval.end;
            }
            else {
                recordStart[index] = Math.min(recordStart[index],interval.start);
                recordEnd[index] = Math.max(recordEnd[index],interval.end);
            }
        }
        List<Interval> result = new ArrayList<Interval>();
        for (int i=0; i<len; i++) {
            result.add(new Interval(recordStart[i],recordEnd[i]));
        }
        return result;
    }
    
    private int binarySearch(int[] record, int low, int high, int target) {
        while (low<=high) {
            int mid = low + (high-low)/2;
            if (record[mid]<target) low = mid+1;
            else if (record[mid]>target) high = mid-1;
            else return low;
        }
        return low;
    }

Log in to reply
 

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