Problem Description
You are given an array of pairs where pairs[i] = [left_i, right_i] and left_i < right_i. 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 of the longest chain which can be formed. You do not need to use up all the given intervals. You can select pairs in any order.
Key Insights
- A chain can be formed by selecting pairs such that the end of one pair is less than the start of the next.
- The problem can be solved using a greedy approach by sorting the pairs based on their end values.
- By iterating through sorted pairs, we can maintain the longest chain by only adding pairs that can follow the last pair in the chain.
Space and Time Complexity
Time Complexity: O(n log n) - due to sorting the pairs.
Space Complexity: O(1) - no additional space is required beyond a few variables for counting.
Solution
The solution involves first sorting the pairs based on their second element (right_i). This allows us to efficiently determine the longest chain by iterating through the sorted list and checking if the current pair can follow the last added pair in the chain. We keep a counter to track the length of the chain.