Leetcode 646) Maximum Length of Pair Chain

12 Aug 2021 in Algorithms

내 답안

• 첫번째 원소로 sort 먼저 한 후, 적절히 증가하는 maximum subsequence dp문제로 찾음.

class Solution {
    public int findLongestChain(int[][] pairs) {
        //이중 어레이 정렬 먼저
        Arrays.sort(pairs, new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2){
                if(o1[0] == o2[0]){
                    return o1[1]-o2[1];
                }else{
                    return o1[0]-o2[0];
                }
            }
        });

        int[] dp = new int[pairs.length+1];
        Arrays.fill(dp,1);
        //값 1줘도 되는지?
        dp[0]=1;
        int max=1;
        for(int i=1;i<pairs.length;i++){
            for(int j=0;j<i;j++){
                if(pairs[i][0]>pairs[j][1]){
                    dp[i]=Math.max(dp[j]+1,dp[i]);
                    max= Math.max(max,dp[i]);
                }
            }
        }
        return max;
    }
}

다른 답안

• Array sort 코드

  • 여기서 2d array를 다음과 같이 정렬했다.

  Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
  

class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
        int N = pairs.length;
        int[] dp = new int[N];
        Arrays.fill(dp, 1);

        for (int j = 1; j < N; ++j) {
            for (int i = 0; i < j; ++i) {
                if (pairs[i][1] < pairs[j][0])
                    dp[j] = Math.max(dp[j], dp[i] + 1);
            }
        }

        int ans = 0;
        for (int x: dp) if (x > ans) ans = x;
        return ans;
    }
}