Merge Intervals - Java Solution - Simple sort & merge


  • 0
    V

    Simple Solution:

    1. Sort all intervals based on their start time
    2. Walk through the sorted list and merge overlapping intervals
        public List<Interval> merge(List<Interval> intervals) {
            if( intervals.size() == 0 || intervals.size() == 1 ) return intervals;
            Collections.sort(intervals, new Comparator<Interval>(){
                @Override
                public int compare(Interval a, Interval b) {
                    if( a.start == b.start )
                        return a.end-b.end;
                    else
                        return a.start-b.start;
                }
            });
            Interval merge = intervals.get(0);
            List<Interval> merged = new LinkedList<Interval>();
            for(int i=1; i<intervals.size(); i++)
            {
                if( intervals.get(i).start > merge.end ) {
                    merged.add(merge);
                    merge = intervals.get(i);
                }
                else
                    merge.end = Math.max(merge.end, intervals.get(i).end);
            }
            /* Add the last merged interval */
            merged.add(merge);
            return merged;
        }
    

Log in to reply
 

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