My solution without sorting start..but may take O(n^2) time


  • -1
    W
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals == null) {
            //throw new Exception();
        }
        
        List<Interval> remains = new ArrayList<Interval>();
        List<Interval> res = new ArrayList<Interval>();
        
        try {
            
            Interval last = null;
            Interval cur = null;
            
            while (!intervals.isEmpty()) {
                for (int i = 0;i < intervals.size();i++) {
                
                    cur = intervals.get(i);
                    
                    if (i == 0) {
                        last = cur;
                        continue;
                    }
                    
                    if (last.end < cur.start || last.start > cur.end) {
                        remains.add(cur);
                    }
                    else {
                        last = new Interval(Math.min(last.start, cur.start), Math.max(last.end, cur.end));
                    }
                }
            
                if (remains.size() + 1 == intervals.size()) {
                    res.add(last);
                }
                else {
                    remains.add(last);
                }
            
                intervals = remains;
                remains = new ArrayList<Interval>();
            }
            
            
        }
        catch(Exception e) {
            //do something..
        }
        
        return res;
    }

Log in to reply
 

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