题解 | #信封嵌套问题#

import java.util.*;


public class Solution {
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param letters int二维数组 
     * @return int
     */
    public int maxLetters(int[][] letters) {
        // write code here
        mergeSort(letters);
        int[] dp = new int[letters.length];
        Arrays.fill(dp, Integer.valueOf(1));
        int ans = 1;
        for (int i = 1; i < letters.length; i++) {
            int[] currentLetter = letters[i];
            for (int j = i - 1; j > -1; j--) {
                int[] previousLetter = letters[j];
                if (currentLetter[0] > previousLetter[0] && currentLetter[1] > previousLetter[1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }

    public void mergeSort(int[][] nums) {
        if (0 == nums.length || 1 == nums.length) {
            return;
        }
        process(nums, 0, nums.length - 1);
    }

    public void process(int[][] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = start + ((end - start) >> 1);
        process(nums, start, mid);
        process(nums, mid + 1, end);
        merge(nums, start, mid, end);
    }

    public void merge(int[][] nums, int start, int mid, int end) {
        int[][] helper = new int[end - start + 1][2];
        int index = 0;
        int p1 = start;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= end) {
            if (nums[p1][0] < nums[p2][0]) {
                helper[index][0] = nums[p1][0];
                helper[index][1] = nums[p1][1];
                index++;
                p1++;
            } else if (nums[p1][0] > nums[p2][0]) {
                helper[index][0] = nums[p2][0];
                helper[index][1] = nums[p2][1];
                index++;
                p2++;
            } else {
                if (nums[p1][1] <= nums[p2][1]) {
                    helper[index][0] = nums[p1][0];
                    helper[index][1] = nums[p1][1];
                    index++;
                    p1++;
                } else if (nums[p1][1] > nums[p2][1]) {
                    helper[index][0] = nums[p2][0];
                    helper[index][1] = nums[p2][1];
                    index++;
                    p2++;
                }
            }
        }
        while (p1 <= mid) {
            helper[index][0] = nums[p1][0];
            helper[index][1] = nums[p1][1];
            index++;
            p1++;
        }
        while (p2 <= end) {
            helper[index][0] = nums[p2][0];
            helper[index][1] = nums[p2][1];
            index++;
            p2++;
        }
        for (int i = 0; i < helper.length; i++) {
            nums[start + i][0] = helper[i][0];
            nums[start + i][1] = helper[i][1];
        }
    }
}