Maximum Length of Pair Chain
Problem
Given an array of n pairs, pair[i] = [a, b], with a < b, a pair (c, d) can follow (a, b) iff b < c. Return the length of the longest chain that can be formed.
pairs = [[1, 2], [2, 3], [3, 4]]2def find_longest_chain(pairs):
pairs.sort(key=lambda p: p[1])
cur_end = float('-inf')
count = 0
for a, b in pairs:
if a > cur_end:
count += 1
cur_end = b
return countfunction findLongestChain(pairs) {
pairs.sort((p, q) => p[1] - q[1]);
let curEnd = -Infinity, count = 0;
for (const [a, b] of pairs) {
if (a > curEnd) { count++; curEnd = b; }
}
return count;
}class Solution {
public int findLongestChain(int[][] pairs) {
Arrays.sort(pairs, (p, q) -> p[1] - q[1]);
int curEnd = Integer.MIN_VALUE, count = 0;
for (int[] p : pairs) {
if (p[0] > curEnd) { count++; curEnd = p[1]; }
}
return count;
}
}int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end(), [](auto& p, auto& q) { return p[1] < q[1]; });
int curEnd = INT_MIN, count = 0;
for (auto& p : pairs) {
if (p[0] > curEnd) { count++; curEnd = p[1]; }
}
return count;
}Explanation
To chain as many pairs as possible, the greedy rule is to always keep the pair that finishes earliest. Finishing early leaves the most room for future pairs, so we sort the pairs by their end value.
We track cur_end, the end of the last pair we accepted, starting at negative infinity. Walking through the sorted pairs, whenever a pair's start a is strictly greater than cur_end, it can follow the chain, so we count it and update cur_end = b.
If a pair's start is not past cur_end, it conflicts with what we already picked, so we skip it.
Example: pairs = [[1,2],[2,3],[3,4]] sorted by end stay the same. We take [1,2] (end 2), skip [2,3] since 2 is not > 2, then take [3,4], giving a chain length of 2.
Choosing earliest-ending pairs is provably optimal, and one sorted pass gives the answer.