0646. Maximum Length of Pair Chain¶
You are given n pairs of numbers. In every pair, the first number is always smaller than the second number.
Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion.
Given a set of pairs, find the length longest chain which can be formed. You needn't use up all the given pairs. You can select pairs in any order.
Example 1:
Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4]
Note:
- The number of given pairs will be in the range [1, 1000].
Analysis¶
tldr: the question is given a list of interval, find the maximum number of intervals can be formed without any intersection.
- two intervals can add to the chain only if first.end < second.first.
For interval question can always use greedy algorithm to solve, and by using greedy is usually sorting. In this question we sort by interval end in ascending order. After sorting, we can do a linear scan to find the maximum size of the chain. If there is an intersection between two consective intervals, we always choose the first one and update our current maximum right boundary. So the question become why do we choose first one instead of the second one? To answer this, we can simulate if we choose the second one from two consective intervals, which means we need to update our right boundary to second.end, where first.end < second.end. To fit in more intervals in the future scan, we should always lower the right boundary, so we shouldn't choose the second one but the first one.
Code¶
class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end(),
[](vector<int>& l, vector<int>& r) {return l[1] < r[1];});
int res = 0;
// note that pairs[i] can be negative, so we init right_bounary to INT_MIN
for (int i = 0, right_bounary = INT_MIN; i < pairs.size(); ++i) {
if (right_bounary < pairs[i][0]) {
right_bounary = pairs[i][1];
res ++;
}
}
return res;
}
};