a readable solution


  • 0
    public class Solution {
        public List<Interval> merge(List<Interval> intervals) {
            if(intervals == null || intervals.size() == 0) {
                return new ArrayList<Interval>();
            }
            Collections.sort(intervals, new Comparator<Interval>(){
                @Override
                public int compare(Interval arg1, Interval arg2){
                    return arg1.start == arg2.start ? arg1.end - arg2.end : arg1.start - arg2.start;
                }
            });
            
            Stack<Interval> stack = new Stack<Interval>();
            for(Interval itv : intervals) {
                if(stack.empty()){
                    stack.push(itv);
                } else {
                    Interval top = stack.peek();
                    if(overlaps(top, itv)) {
                        top.start = Math.min(top.start, itv.start);
                        top.end = Math.max(top.end, itv.end);
                    } else {
                        stack.push(itv);
                    }
                }
            }
            return new ArrayList<Interval>(stack);
        }
        
        public boolean overlaps(Interval arg1, Interval arg2){
            return !(arg1.end < arg2.start || arg2.end < arg1.start);
        }
    }
    

Log in to reply
 

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