@@ -0,0 +1,2786 @@
+/**%0A * Created by fang on 4/22/17.%0A */%0Aimport java.util.*;%0A%0Apublic class MergeIntervals %7B%0A      public static class Interval %7B%0A          public int start;%0A          public int end;%0A%0A%0A          public Interval(int s, int e) %7B%0A              start = s;%0A              end = e;%0A          %7D%0A      %7D%0A%0A%0A    public List%3CInterval%3E merge(List%3CInterval%3E intervals) %7B%0A        List%3CInterval%3E res = new LinkedList%3C%3E();%0A        if(intervals.size()==0)%7B%0A            return res;%0A        %7D%0A        sort(intervals);%0A        Interval start = new Interval(intervals.get(0).start,intervals.get(0).end);%0A        res.add(start);%0A        for(int i=1;i%3Cintervals.size();i++)%7B%0A            Interval next = intervals.get(i);%0A            Interval pre = res.get(res.size()-1);%0A            if(pre.end%3E=next.start)%7B%0A                pre.end =  pre.end%3Enext.end? pre.end:next.end;%0A                continue;%0A            %7D%0A            Interval newElem = new Interval(next.start,next.end);%0A            res.add(newElem);%0A        %7D%0A        return res;%0A    %7D%0A%0A    private void sort(List%3CInterval%3E intervals)%7B%0A        for(int i=0;i%3Cintervals.size();i++)%7B%0A            for(int j=i+1;j%3Cintervals.size();j++)%7B%0A                Interval pre = intervals.get(i);                      //the slection sort here should pay attentation%0A                Interval next = intervals.get(j);%0A                if(pre.start%3Enext.start)%7B%0A                    Collections.swap(intervals, i, j);%0A                %7D%0A            %7D%0A        %7D%0A    %7D%0A%0A    private void quicksort(List%3CInterval%3E intervals,int s, int e)%7B%0A        if(s%3Ce)%7B%0A            int index = partition(intervals,s,e);%0A            quicksort(intervals,s,index-1);%0A            quicksort(intervals,index+1,e);%0A        %7D%0A    %7D%0A%0A    private int partition(List%3CInterval%3Eintervals,int s, int e)%7B%0A        Interval pivot = intervals.get(e);%0A        int l = s-1;%0A        for(int i=s;i%3Ce;i++)%7B%0A            if(intervals.get(i).start%3C=pivot.start)%7B%0A                l++;%0A                Collections.swap(intervals,i,l);%0A            %7D%0A        %7D%0A        Collections.swap(intervals,l+1,e);%0A        return l+1;%0A    %7D%0A%0A//    public static void main(String%5B%5D args)%7B%0A//          List%3CInterval%3E intervals = new LinkedList%3C%3E();%0A//          MergeIntervals solution = new MergeIntervals();%0A//          Interval one = new Interval(1,3);%0A//          intervals.add(one);%0A//          Interval two = new Interval(2,6);%0A//          Interval three = new Interval(7,10);%0A//          Interval four = new Interval(8,12);%0A//%0A//          intervals.add(two);%0A//          intervals.add(three);%0A//          intervals.add(four);%0A//          List%3CInterval%3E res = solution.merge(intervals);%0A//          for(int i=0;i%3Cres.size();i++)%7B%0A//              System.out.print(res.get(i).start+%22 %22+res.get(i).end+%22 %22);%0A//          %7D%0A//%0A//    %7D%0A%7D%0A%0A

The solution for problem 56