Easy to understand Java Solution


  • 0
    R

    First Sort the list by using a custom comparator which sorts based on start of the interval.

    Then compare the first two intervals if they need to be merged.

    • If the end of first interval is less than start of second interval then no merging is required

    • Else merging is required them.
      - remove the two intervals and add the merged interval.

    • move to next two intervals.

    • Continue this till you reach last two intervals.

    • return the merged intervals.

       public List<Interval> merge(List<Interval> intervals) {
           
           	Comparator<Interval> cmp = new Comparator<Interval>()
           			{
           		@Override
           		public int compare(Interval s1, Interval s2){
           			if(s1.start==s2.start){
           				return 0;
           			}
           			else if(s1.start>s2.start){
           				return 1;
           			}
           			else
           				return -1;
           		}
           			};
           			Collections.sort(intervals, cmp);
           
           			int i= intervals.size();
           			int j=0,k=0;
           			while(j<i-1){
           				if(intervals.get(k).end<intervals.get(k+1).start){
           					j++;
           					k++;
           				}
           				else{
           					Interval it = new Interval(Math.min(intervals.get(k).start,intervals.get(k+1).start),Math.max(intervals.get(k).end,intervals.get(k+1).end));
           					intervals.remove(k);
           					intervals.remove(k);
           					intervals.add(k,it);
           					j++;
           				}
           			}
           			return intervals;
      

      }


Log in to reply
 

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