Skip to content

Instantly share code, notes, and snippets.

@wayetan
Created March 5, 2014 09:43
Show Gist options
  • Save wayetan/9364210 to your computer and use it in GitHub Desktop.
Save wayetan/9364210 to your computer and use it in GitHub Desktop.
Merge Intervals
/**
* 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 Solution {
public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
ArrayList<Interval> res = new ArrayList<Interval>();
if(intervals == null || intervals.size() == 0)
return res;
Collections.sort(intervals, new Comparator<Interval>(){
public int compare(Interval a, Interval b) {
return a.start > b.start ? 1 : (a.start == b.start ? 0 : -1);
}
});
for(int i = 0; i < intervals.size(); i++) {
Interval cur = intervals.get(i);
if(res.isEmpty()) {
res.add(cur);
} else {
Interval last = res.get(res.size() - 1);
if(last.end >= cur.start) {
// merge
last.end = Math.max(last.end, cur.end);
} else {
res.add(cur);
}
}
}
return res;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment