Merge Intervals (Java)

LeetCode

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Solution:

Sort the list base on start valuable in an interval, then a while loop merge every overlap interval.

	Given a collection of intervals, merge all overlapping intervals.
	For example,
	Given [1,3],[2,6],[8,10],[15,18],
	return [1,6],[8,10],[15,18].
	/**
	* Definition for an interval.
	* public class Interval {
	* int start;
	* int end;
	* Interval() { start = 0; end = 0; }
	* Interval(int s, int e) { start = s; end = e; }
	* }
	*/
	public class MergeIntervals {
	public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
	if (intervals==null ||intervals.size()<2){
	return intervals;
	}
	ArrayList<Interval> result=new ArrayList<Interval>();
	Comparator<Interval> intervalComperator=new Comparator<Interval>(){
	public int compare(Interval i1, Interval i2){
	Integer i1St=i1.start;
	Integer i2St=i2.start;
	return i1St.compareTo(i2St);
	}
	};
	Collections.sort(intervals, intervalComperator);
	Interval current=intervals.get(0);
	int i=1;
	while (i<intervals.size() ){
	Interval currentToCompare=intervals.get(i);
	if (current.end<currentToCompare.start){
	result.add(current);
	current=currentToCompare;
	}
	else{
	current.end=Math.max(current.end, currentToCompare.end);
	}
	i++;
	}
	result.add(current);
	return result;
	}
	}

view raw MergeIntervals.java hosted with ❤ by GitHub