package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode.com/problems/merge-intervals/
 */
public class Problem56 {
    public static class Interval {
        int start;
        int end;

        Interval() {
            start = 0;
            end = 0;
        }

        Interval(int s, int e) {
            start = s;
            end = e;
        }

        @Override
        public String toString() {
            return "[" + start + ", " + end + "]";
        }
    }

    public List<Interval> merge(List<Interval> intervals) {
        // TODO
        return new ArrayList<>();
    }

    public static void main(String[] args) {
        Problem56 prob = new Problem56();
        System.out.println(prob.merge(Arrays.asList(new Interval[]{
            new Interval(1, 3),
            new Interval(2, 6),
            new Interval(8, 10),
            new Interval(15, 18)
        }))); // [1,6], [8,10], [15,18]
    }
}

@@ -57,21 +57,26 @@
 va.util.
-Array
+Collection
 s;%0Aimpor
@@ -416,189 +416,261 @@
   %7D%0A
-%0A
     
+%7D%0A%0A
     
-@Override%0A        public String toString() %7B%0A            return %22%5B%22 + start + %22, %22 + end + %22%5D%22;%0A        %7D
+public List%3CInterval%3E merge(List%3CInterval%3E intervals) %7B%0A        Collections.sort(intervals, (a, b) -%3E %7B%0A            int cmp = Integer.compare(a.start, b.start);%0A            if (cmp == 0) %7B
 %0A    
-%7D%0A%0A
     
-public List%3CInterval%3E merge(List%3CInterval%3E intervals) %7B
+        return Integer.compare(a.end, b.end);
 %0A   
@@ -678,24 +678,23 @@
     
-// TODO%0A
+    %7D%0A 
         
 retu
@@ -689,22 +689,74 @@
         
+   
 return
+ cmp;%0A        %7D);%0A        List%3CInterval%3E result =
  new Arr
@@ -775,254 +775,539 @@
     
-%7D%0A%0A
     
-public static void main(String%5B%5D args) %7B%0A        Problem56 prob
+result.add(intervals.get(0));%0A        for (int i = 1; i %3C intervals.size(); i++) %7B%0A            Interval prev
  = n
-ew Problem56();%0A        System.out.println(prob.merge(Arrays.asList(new Interval%5B%5D%7B%0A            new Interval(1, 3),%0A            new Interval(2, 6),%0A           
+ull;%0A            if (result.isEmpty()) %7B%0A                prev = intervals.get(i - 1);%0A            %7D else %7B%0A                prev = result.get(result.size() - 1);%0A            %7D%0A            Interval curr = intervals.get(i);%0A            if (prev.end %3E= curr.start) %7B%0A                Interval newInterval = new Interval(prev.start, Math.max(curr.end, prev.end));%0A                result.set(result.size() - 1,
  new
- 
 Interval
 (8, 
@@ -1306,16 +1306,10 @@
 rval
-(8, 10),
+);
 %0A   
@@ -1321,68 +1321,97 @@
     
-new Interval(15, 18)%0A        %7D))); // %5B1,6%5D, %5B8,10%5D, %5B15,18%5D
+%7D else %7B%0A                result.add(curr);%0A            %7D%0A        %7D%0A        return result;
 %0A   

Solve problem 56