[leetcode]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 27 28 29 30 31 32 33 34 35 36 37 38 39

public class Solution { public List<Interval> merge(List<Interval> intervals) { List<Interval> result = new ArrayList<Interval>(); if (intervals == null || intervals.size() == 0) return result; PriorityQueue<Interval> queue = new PriorityQueue<Interval>(intervals.size(), new Comparator<Interval>(){ public int compare(Interval in1, Interval in2){ return in1.start-in2.start; } }); for (int i = 0; i < intervals.size(); i++){ queue.add(intervals.get(i)); } while (!queue.isEmpty()){ Interval temp = queue.poll(); if (result.isEmpty()) result.add(temp); else{ Interval last = result.get(result.size()-1); if (isOverlapped(last, temp)){ result.remove(result.size()-1); result.add(mergeTwoIntervals(last, temp)); }else{ result.add(temp); } } } return result; } private Interval mergeTwoIntervals(Interval in1, Interval in2){ return new Interval(Math.min(in1.start, in2.start), Math.max(in1.end, in2.end)); } private boolean isOverlapped(Interval in1, Interval in2){ if (in1.start > in2.end || in1.end < in2.start) return false; return true; } }