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
- This is the classic activity-selection problem: choose the maximum number of non-overlapping intervals.
- Sort the pairs by their right endpoint ascending.
- Greedily take a pair whenever its left endpoint exceeds the last taken right endpoint.
- 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 >= curinstead ofa > 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
curtopairs[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.