Simple Java algorithm


  • 0
    L

    The idea is to avoid doing n^2 by sorting. Add an interval first and then for susequent intervals, merge together if those are overlapping and extend the end time. If a subsequent interval lies within the previous event just ignore that.

    public List<Interval> merge(List<Interval> intervals) {
            Collections.sort(intervals,(x,y)->{
               if(x.start!=y.start) {
                   return x.start-y.start;
               } 
               else {
                   return x.end-y.end;     
               }
            });
            
            List<Interval> list = new ArrayList<>();
            for(Interval current : intervals) {
                if(!list.isEmpty()) {
                    Interval last = list.get(list.size()-1);
                    if(current.start<=last.end) {//overlap.
                        if(current.end >last.end) {
                            last.end = current.end;                        
                        }
                        continue;
                    }                
                }
                list.add(current);
            }
            return list;
        }
    

Log in to reply
 

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