[LintCode] Merge Intervals
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
public List<Interval> merge(List<Interval> intervals) { // write your code here List<Interval> res= new ArrayList<Interval>(); if(intervals.size() == 0 || intervals == null) return res; Collections.sort(intervals, new IntervalComparator()); Interval first = intervals.get(0); for(int i = 1; i < intervals.size(); i++) { Interval cur = intervals.get(i); if(cur.start <= first.end) { first.end = Math.max(cur.end, first.end); }else{ res.add(first); first = cur; } } res.add(first); return res; } class IntervalComparator implements Comparator{ public int compare(Object o1, Object o2){ Interval i1 = (Interval)o1; Interval i2 = (Interval)o2; return i1.start - i2.start; } } |
Leave A Comment