package com.fishercoder.solutions;

import java.util.Arrays;

/**
 * 354. Russian Doll Envelopes
 *
 * You have a number of envelopes with widths and heights given as a pair of integers (w, h).
 * One envelope can fit into another if and only if both the width and height of one envelope is greater than
 * the width and height of the other envelope.

 What is the maximum number of envelopes can you Russian doll? (put one inside other)

 Example:
 Given envelopes = [[5,4],[6,4],[6,7],[2,3]], the maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

 */
public class _354 {
    /**reference: https://discuss.leetcode.com/topic/47469/java-nlogn-solution-with-explanation*/
    public int maxEnvelopes(int[][] envelopes) {
        if (envelopes == null || envelopes.length == 0
                || envelopes[0].length == 0 || envelopes[0].length != 2) {
            return 0;
        }
        Arrays.sort(envelopes, (int[] a, int[] b) -> {
                    if (a[0] == b[0]) {
                        return b[1] - a[1];
                    } else {
                        return a[0] - b[0];
                    }
                }
        );
        int[] dp = new int[envelopes.length];
        int len = 0;
        for (int[] envelope : envelopes) {
            int index = Arrays.binarySearch(dp, 0, len, envelope[1]);
            if (index < 0) {
                index = -(index + 1);
            }
            dp[index] = envelope[1];
            if (index == len) {
                len++;
            }
        }
        return len;
    }
}

@@ -602,15 +602,56 @@
 4 %7B%0A
+    public static class Solution1 %7B%0A    
     /**
+ 
 refe
@@ -734,19 +734,24 @@
 lanation
+ 
 */%0A
+    
     publ
@@ -795,24 +795,28 @@
 ) %7B%0A        
+  
+  
 if (envelope
@@ -933,24 +933,28 @@
             
+    
 return 0;%0A  
@@ -951,34 +951,42 @@
 turn 0;%0A        
-%7D%0A
+    %7D%0A    
         Arrays.s
@@ -1229,19 +1229,27 @@
         
+  
+  
 );%0A
+    
         
@@ -1290,24 +1290,28 @@
 h%5D;%0A        
+  
+  
 int len = 0;
@@ -1307,24 +1307,28 @@
 nt len = 0;%0A
+    
         for 
@@ -1366,24 +1366,28 @@
             
+  
+  
 int index = 
@@ -1436,32 +1436,36 @@
 %5D);%0A            
+    
 if (index %3C 0) %7B
@@ -1481,16 +1481,20 @@
         
+  
+  
 index = 
@@ -1511,34 +1511,40 @@
 1);%0A            
-%7D%0A
+    %7D%0A  
             dp%5Bi
@@ -1539,16 +1539,18 @@
         
+  
 dp%5Bindex
@@ -1570,32 +1570,36 @@
 1%5D;%0A            
+    
 if (index == len
@@ -1618,16 +1618,20 @@
         
+  
+  
 len++;%0A 
@@ -1645,20 +1645,32 @@
     
-%7D%0A    
     %7D%0A
+            %7D%0A    
     
@@ -1685,16 +1685,26 @@
 rn len;%0A
+        %7D%0A
     %7D%0A%7D%0A

refactor 354