Hey Guys!, Welcome to day 84. Today we are going to solve today's daily leetcode problem. So let's get right into it.
Question: 646. Maximum Length of Pair Chain
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.
Examples:
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].
Intuition: Greedy Approach
The greedy approach is based on the idea of selecting pairs in a way that maximizes the length of the valid chain. The goal is to find a sequence of pairs where each pair (a, b) is followed by a pair (c, d) such that b < c. The key insight is to sort the pairs in ascending order based on the second element b. This sorting ensures that pairs with smaller b values are placed earlier in the sequence, making it more likely to find valid chains.
Algorithm:
- Define a custom comparison function named
compSort
that compares two pairs based on the second element (b
) of each pair. - Sort the given list of pairs in ascending order using the
compSort
comparison function. - Initialize a variable
cur
to store the current ending value of the chain. Set it initially to a very small value (INT_MIN
). - Initialize a variable
count
to keep track of the length of the longest chain. Set it initially to 0. - Iterate through each pair in the sorted list:
- If the current pair's first element
a
is greater than the current ending valuecur
, updatecur
to the second elementb
of the current pair, and increment thecount
. - If the condition is not met, move on to the next pair without updating
cur
.
- If the current pair's first element
- Return the final value of
count
, which represents the length of the longest chain of pairs.
Code:
class Solution {
public:
int helper(int index, int prev, vector<vector<int>>& pairs, vector<vector<int>>&dp){
if(index == pairs.size()) return 0;
if(dp[index][prev+1] != -1) return dp[index][prev+1];
int pick = -1e9;
int notPick = helper(index+1,prev,pairs,dp);
if(prev == -1 || pairs[prev][1] < pairs[index][0]){
pick = 1 + helper(index+1,index,pairs,dp);
}
return dp[index][prev+1] = max(pick,notPick);
}
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(),pairs.end());
vector<vector<int>> dp(pairs.size(),vector<int>(pairs.size()+1,-1));
return helper(0,-1,pairs,dp);
}
};
Complexity Analysis:
Complexity | Analysis |
---|---|
Time | O(n * log n) |
Space | O(1) |
Top comments (0)