|
| 1 | +packagehard; |
| 2 | +importjava.util.*; |
| 3 | +importclasses.Interval; |
| 4 | +importutils.CommonUtils; |
| 5 | + |
| 6 | +/** |
| 7 | + * Created by fishercoder1534 on 10/3/16. |
| 8 | + */ |
| 9 | +publicclassMergeIntervals { |
| 10 | + |
| 11 | +/**Inspired by this post: https://discuss.leetcode.com/topic/4319/a-simple-java-solution |
| 12 | + * 1. Sort the intervals first, based on their starting point |
| 13 | + * 2. then compare the end point with next interval's start point, if they overlap, then update the end point to the longest one, |
| 14 | + * if they don't overlap, we add it into the result and continue the iteration.*/ |
| 15 | +publicstaticList<Interval>merge(List<Interval>intervals) { |
| 16 | +if(intervals.size() <=1)returnintervals; |
| 17 | + |
| 18 | +Collections.sort(intervals,newComparator<Interval>() { |
| 19 | +@Override |
| 20 | +publicintcompare(Intervalo1,Intervalo2) { |
| 21 | +returno1.start -o2.start; |
| 22 | + } |
| 23 | + }); |
| 24 | + |
| 25 | +List<Interval>result =newArrayList(); |
| 26 | +for(inti =0;i <intervals.size();i++){ |
| 27 | +intstart =intervals.get(i).start; |
| 28 | +intend =intervals.get(i).end; |
| 29 | +while(i <intervals.size() &&end >=intervals.get(i).start){ |
| 30 | +end =Math.max(end,intervals.get(i).end); |
| 31 | +i++; |
| 32 | + } |
| 33 | +result.add(newInterval(start,end)); |
| 34 | +i--; |
| 35 | + } |
| 36 | +returnresult; |
| 37 | + } |
| 38 | + |
| 39 | +publicstaticvoidmain(String[]args){ |
| 40 | +List<Interval>list =newArrayList<Interval>(); |
| 41 | +// //test case 1: |
| 42 | +// list.add(new Interval(2,3)); |
| 43 | +// list.add(new Interval(5,5)); |
| 44 | +// list.add(new Interval(2,2)); |
| 45 | +// list.add(new Interval(3,4)); |
| 46 | +// list.add(new Interval(3,4)); |
| 47 | + |
| 48 | +//test case 2: |
| 49 | +list.add(newInterval(1,3)); |
| 50 | +list.add(newInterval(2,6)); |
| 51 | +list.add(newInterval(8,10)); |
| 52 | +list.add(newInterval(15,18)); |
| 53 | +CommonUtils.printList(merge(list)); |
| 54 | + } |
| 55 | + |
| 56 | +} |