646. Maximum Length of Pair Chain / TypeScript

You are given an array of n pairs pairs where pairs[i] = [lefti, righti] and lefti < righti.

A pair p2 = [c, d] follows a pair p1 = [a, b] if b < c. A chain of pairs can be formed in this fashion.

Return the length longest chain which can be formed.

You do not need to use up all the given intervals. You can select pairs in any order.

 

Example 1:

Input: pairs = [[1,2],[2,3],[3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4].

Example 2:

Input: pairs = [[1,2],[7,8],[4,5]]
Output: 3
Explanation: The longest chain is [1,2] -> [4,5] -> [7,8].

 

출처 : https://leetcode.com/problems/maximum-length-of-pair-chain/description/ 

 

풀이 

 

function findLongestChain(pairs: number[][]): number {
    pairs = pairs.sort((a, b) => a[1] - b[1]);
    let current: number = Number.NEGATIVE_INFINITY;
    let answer: number = 0;

    for(const [a, b] of pairs) {
        if (a > current) {
            answer++;
            current = b;
        }
    }

    return answer;
};

 

주어진 숫자 쌍들(pairs)로부터 가장 긴 체인을 찾는 함수

 

예시

const pairs = [[1, 2], [2, 3], [3, 4]];

 

 

• 정렬 단계:
  
  • 정렬된 배열: [[1, 2], [2, 3], [3, 4]]
• 변수 초기화:
  • current를 음의 무한대로 초기화: current = Number.NEGATIVE_INFINITY
  • answer를 0으로 초기화: answer = 0
• 루프를 통해 체인 찾기:
  • 첫 번째 쌍 [1, 2]에 대해:
    • a = 1, b = 2
    • a > current (1 > -∞) 조건을 만족하므로:
      • answer를 1 증가: answer = 1
      • current를 b로 업데이트: current = 2
  • 두 번째 쌍 [2, 3]에 대해:
    • a = 2, b = 3
    • a > current (2 > 2) 조건을 만족하지 않으므로 아무 작업도 하지 않음.
  • 세 번째 쌍 [3, 4]에 대해:
    • a = 3, b = 4
    • a > current (3 > 2) 조건을 만족하므로:
      • answer를 1 증가: answer = 2
      • current를 b로 업데이트: current = 4
• 최종 결과 반환:
  • 모든 쌍을 순회한 후 answer는 가장 긴 체인의 길이를 나타내며, 이 경우 answer = 2