My awesome solution


  • 0
    A
    public class Solution {
        public List<Interval> merge(List<Interval> intervals) {
            Collections.sort(intervals, c);
            Iterator<Interval> it = intervals.iterator();  
            Interval curr = null;
            if(it.hasNext())
                 curr = it.next();
             while(it.hasNext()){
                 Interval tmp = it.next();
                 if(tmp.start <= curr.end){            
                     curr.end = Math.max(tmp.end, curr.end);
                     it.remove();
                 }else
                    curr = tmp;
                
             }        
             return intervals;       
        }
          
        private static final Comparator<Interval> c = new Comparator<Interval>(){
           @Override
           public int compare(Interval a, Interval b)
           {
               if(a.start != b.start)
                   return a.start - b.start;
               else 
                   return a.end - b.end;      
           }
        };      
    }

  • 0
    G

    Since you already sorted the intervals, you don't have to do a "list remove" for each merge. Do X merges, and remove X elements at once. That can save a lot of time because remove operation really is O(N).


  • 0
    A

    Thank for your suggestion. But I am not sure how removing X elements at once would save a lot of time. If you are talking about having a to-be-deleted list of intervals, and call removeAll method, then it wouldn't going to save time because ...

    public boolean removeAll(Collection<?> c) {
        boolean modified = false;
        Iterator<?> e = iterator();
        while (e.hasNext()) {
            if (c.contains(e.next())) {
                e.remove();
                modified = true;
            }
        }
        return modified;
    }
    

    Otherwise, please let me know what do you have in mind.


  • 0
    G

    After sorting, an Interval only can merge with its neighbors. Say, Interval[i] can merge with Interval[i+1...i+j], then after we do j merges (but not vector.erase()), we use one vector.erase() to remove Interval[i+1...i+j].

    Why? vector.erase() has a complexity of O(N). I am not sure if my solution runs faster than yours on OJ. Maybe it is just a small improvement. My solution runs in 612 ms (looks like this question has some big test case).


Log in to reply
 

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