package leetcode;

import java.util.ArrayList;
import java.util.Collections;
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;
        }
    }

    public List<Interval> merge(List<Interval> intervals) {
        Collections.sort(intervals, (a, b) -> {
            int cmp = Integer.compare(a.start, b.start);
            if (cmp == 0) {
                return Integer.compare(a.end, b.end);
            }
            return cmp;
        });
        List<Interval> result = new ArrayList<>();
        result.add(intervals.get(0));
        for (int i = 1; i < intervals.size(); i++) {
            Interval prev = null;
            if (result.isEmpty()) {
                prev = intervals.get(i - 1);
            } else {
                prev = result.get(result.size() - 1);
            }
            Interval curr = intervals.get(i);
            if (prev.end >= curr.start) {
                Interval newInterval = new Interval(prev.start, Math.max(curr.end, prev.end));
                result.set(result.size() - 1, newInterval);
            } else {
                result.add(curr);
            }
        }
        return result;
    }
}

@@ -70,16 +70,45 @@
 ctions;%0A
+import java.util.Comparator;%0A
 import j
@@ -282,84 +282,8 @@
 d;%0A%0A
-        Interval() %7B%0A            start = 0;%0A            end = 0;%0A        %7D%0A%0A
     
@@ -369,199 +369,269 @@
   %7D%0A
-    %7D%0A%0A    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
+%0A        @Override%0A        public String toString() %7B%0A            return %22%5B%22 + start + %22, %22 + end + %22%5D%22;%0A        %7D%0A    %7D%0A%0A    public List%3CInterval%3E merge(List%3CInterval%3E intervals) %7B%0A        List%3CInterval%3E answer = new ArrayList%3C%3E();%0A        if (intervals.size()
  == 
@@ -651,149 +651,178 @@
     
-    
 return 
-Integer.compare(a.end, b.end);%0A            %7D%0A            return cmp;%0A        %7D);%0A        List%3CInterval%3E result = new ArrayList%3C%3E()
+answer;%0A        %7D%0A        Collections.sort(intervals,%0A            Comparator.comparingInt((Interval a) -%3E a.start).thenComparingInt(a -%3E a.end));%0A        int i = 0
 ;%0A  
@@ -823,30 +823,30 @@
  0;%0A        
-result
+answer
 .add(interva
@@ -852,17 +852,19 @@
 als.get(
-0
+i++
 ));%0A    
@@ -871,24 +871,15 @@
     
-for (int i = 1; 
+while (
 i %3C 
@@ -898,13 +898,8 @@
 ze()
-; i++
 ) %7B%0A
@@ -923,56 +923,124 @@
 val 
-prev = null;%0A            if (result.isEmpty()) %7B
+lastAnswer = answer.get(answer.size() - 1);%0A            if (lastAnswer.end %3C intervals.get(i).start) %7B // no overlap
 %0A   
@@ -1052,23 +1052,27 @@
         
-prev = 
+answer.add(
 interval
@@ -1078,20 +1078,17 @@
 ls.get(i
- - 1
+)
 );%0A     
@@ -1123,147 +1123,77 @@
     
-prev = result.get(result.size() - 1);%0A            %7D%0A            Interval curr = intervals.get(i);%0A            if (prev.end %3E= curr
+int minStart = Integer.min(lastAnswer.start, intervals.get(i)
 .start)
- %7B
+;
 %0A   
@@ -1209,85 +1209,70 @@
     
-Interval newInterval = new Interval(prev.start, Math.max(curr.end, prev
+int maxEnd = Integer.max(lastAnswer.end, intervals.get(i)
 .end)
-)
 ;%0A  
@@ -1289,25 +1289,25 @@
     
-result.set(result
+answer.set(answer
 .siz
@@ -1318,24 +1318,25 @@
 - 1, new
+ 
 Interval
 );%0A     
@@ -1327,16 +1327,34 @@
 Interval
+(minStart, maxEnd)
 );%0A     
@@ -1353,39 +1353,32 @@
 );%0A            %7D
- else %7B
 %0A               
@@ -1378,43 +1378,12 @@
     
-    result.add(curr);%0A            %7D
+i++;
 %0A   
@@ -1408,14 +1408,14 @@
 urn 
-result
+answer
 ;%0A  

Update problem 56