⚡Flashcard Drill➔
NeetCode #799LC-646MediumGreedy
← Back to All Problems

#799 · #646 · Maximum Length of Pair Chain(最长数对链)

📌 Problem Statement & Constraints

You are given n pairs where pairs[i] = [left, right] and left < right. A pair [c, d] can follow [a, b] in a chain if b < c. Return the length of the longest chain. Constraints: 1 <= n <= 1000, -1000 <= left < right <= 1000.

💡 Core Algorithmic Approaches

  1. This is the classic activity-selection problem: choose the maximum number of non-overlapping intervals.
  2. Sort the pairs by their right endpoint ascending.
  3. Greedily take a pair whenever its left endpoint exceeds the last taken right endpoint.
  4. Sorting by the end is optimal because finishing earlier leaves more room for subsequent pairs.

💻 Benchmark Python3 Implementation

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        pairs.sort(key=lambda p: p[1])     # by right endpoint
        cur = float("-inf")
        res = 0
        for a, b in pairs:
            if a > cur:                    # strictly greater, per the rule
                res += 1
                cur = b
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n): the sort dominates.
💾 Space Complexity
O(1) beyond the sort.

⚠️ Interview Pitfalls & Follow-ups

  • Sorting by the left endpoint: that is the interval-scheduling trap; sorting by the right endpoint is what makes the greedy optimal.
  • Using a >= cur instead of a > cur: the chain condition is strict, b < c.
  • Using DP: the O(n^2) longest-chain DP is correct but slower than the greedy.
  • Initialising cur to pairs[0][1]: starting from negative infinity lets the first pair be taken naturally.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems