Merge Intervals Solution


  • 0
    L

    The solution for this problem is derived around following ideas -

    Let the interval of A be [Sa, Ea] and that of B be [Sb, Eb]. Following are the exhaustive cases.

    1. If interval A finishes before interval B starts {Ea < Sb}, include both the intervals.
    2. If interval A starts before interval B and ends after interval B { Sa < Sb, Ea > Eb}, include only interval A.
    3. If interval B starts before interval A finishes {Sb<Ea}, include [Sa, Eb]

    First, we have to sort the intervals according to their start times for this.

    Code -

    class Solution {
        
        class IntervalComparator implements Comparator<Interval>
    {
        public int compare(Interval a, Interval b)
        {
            if(a.start!=b.start)
                return a.start-b.start;
            else 
                return a.end-b.end;
                
        }
    }
        public List<Interval> merge(List<Interval> intervals) {
            if(intervals==null || intervals.size()<2)
                return intervals;
            else
            {
               Collections.sort(intervals, new IntervalComparator());
                List<Interval> returnList = new ArrayList<Interval>();
                Interval current = intervals.get(0);
                Interval next = null;
                for(int i=1;i<intervals.size();i++)
                {
                    next = intervals.get(i);
                    if(next.start > current.end)
                    {
                        returnList.add(current);
                        current = next;
                    }
                    else
                    {
                        current.end = Math.max(current.end, next.end);
                    }
                }
                returnList.add(current);
                return returnList;
            }
            
        }
    }
    

    This changes the input list. If there is a constraint of not modifying the input list, we can clone the objects.


Log in to reply
 

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