Sharing my ac solution, 8ms, beats 98%


  • 0
    B

    Use the logic in "57 - insert interval" problem, starting inserting one by one and merging with the ones in the list.

    public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        
        List<Interval> result = new ArrayList<Interval>();
        for (Interval i : intervals)
            result = helper(result, i);
        return result;
            
    }
    
    private List<Interval> helper(List<Interval> itv, Interval newOne){
        
        List<Interval> result = new ArrayList<Interval>();
        //assume itv has no overlapping and sorted by start
        int i = 0;
        //find ones that ends before new one
        while (i < itv.size() && itv.get(i).end < newOne.start){
            result.add(itv.get(i++));
        }
        
        if (i == itv.size())
            result.add(newOne);
        else{
            
            //find ones that are overlapping
            Interval temp = newOne;
            while (i < itv.size() && itv.get(i).start <= newOne.end){
                temp.start = Math.min(temp.start, itv.get(i).start);
                temp.end = Math.max(temp.end, itv.get(i).end);
                i++;
            }
            
            result.add(temp);
            
            //add the rest if any
            while (i < itv.size())
                result.add(itv.get(i++));
        }
        
        return result;
    }
    
    }

Log in to reply
 

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