leetcode RussianDollEnvelopes
z
 2019-04-09 10:36:27   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import java.util.Collections;

public class RussianDollEnvelopes {
  /**
   * 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)
   *
   * Note:
   * Rotation is not allowed.
   *
   * Example:
   *
   * Input: [[5,4],[6,4],[6,7],[2,3]]
   * Output: 3
   * Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7])
   */
  public int maxEnvelopes(int[][] envelopes) {
    if (envelopes.length == 0 || envelopes == null) return 0;
    int n = envelopes.length;
    int[] dp = new int[envelopes.length];
    sort(envelopes);
    int max_count=0;
    int max_idx = 0;
    for (int i=1; i<envelopes.length; i++){
      for (int j=0; j<i; j++){
        if (envelopes[i][0]>envelopes[j][0] && envelopes[i][1]>envelopes[j][1]){
          dp[i] = Math.max(dp[i], dp[j] + 1);
          if (dp[i] > max_count){
            max_count = dp[i];
            max_idx = i;
          }
        }
      }
    }
    return dp[max_idx]+1;

  }
  public static void sort(int[][] envelopes){
    for (int i=1; i<envelopes.length; i++){
      for (int j=0; j<i; j++){
        if (envelopes[i][0]<envelopes[j][0]){
          int[] temp = envelopes[i];
          envelopes[i] = envelopes[j];
          envelopes[j] = temp;
        }
        else if (envelopes[i][1]==envelopes[j][1]){
          if (envelopes[i][1] < envelopes[j][1]){
            int[] temp = envelopes[i];
            envelopes[i] = envelopes[j];
            envelopes[j] = temp;
          }
        }
      }
    }



  }
  public static void main(String[] args){
    int[][] test = new int[][]{{5,4},{6,4},{6,7},{2,3}};
    sort(test);
    for (int[] a: test){
      System.out.println(a[0] + " " + a[1]);
    }
  }
}