Maximum Length of Pair Chain
Understanding the Problem
This problem is about selecting the maximum number of pairs that can form a chain, where each pair's start must be strictly greater than the previous pair's end. We can pick pairs in any order, not just the order they appear in the input, so we are free to sort or rearrange them however we like.
This is the activity selection problem in different clothing. Activity selection asks: given a set of activities with start and end times, find the maximum number of non-overlapping activities. Each pair [a, b] is an interval, and the chain condition b < c means the next pair must start strictly after the previous one ends (no overlap, and not even touching endpoints).
Key Constraints:
1 <= n <= 1000-> With n up to 1,000, an O(n^2) solution does about 1 million operations, which runs well within typical time limits. So even the O(n^2) DP below is fast enough.-1000 <= left_i < right_i <= 1000-> The values fit comfortably in a 32-bit integer, so there is no overflow concern. Each pair hasleft < right, so there are no zero-length intervals to worry about.- "You can select pairs in any order" -> Because order is free, sorting the input is allowed and is what makes both approaches below work.
Approach 1: Dynamic Programming
Intuition
Building a chain is structurally the same as building a Longest Increasing Subsequence (LIS), except that instead of comparing single values we compare intervals. A pair can extend a chain only if it starts after the previous pair ends.
Sort the pairs by their first element, then for each pair look at all previous pairs and check whether they can precede it. If pair j can precede pair i (meaning pairs[j][1] < pairs[i][0]), then the longest chain ending at i is at least one more than the longest chain ending at j. Sorting by the first element guarantees every pair that could precede i appears before i in the array, so a single left-to-right scan considers all candidates.
Algorithm
- Sort
pairsby the first element. - Create a
dparray wheredp[i]represents the length of the longest chain ending withpairs[i]. - Initialize every
dp[i] = 1(each pair alone forms a chain of length 1). - For each pair
i, look at all pairsj < i. Ifpairs[j][1] < pairs[i][0], thendp[i] = max(dp[i], dp[j] + 1). - Return the maximum value in the
dparray.
Example Walkthrough
Input:
The pairs are already sorted by first element. We initialize dp = [1, 1, 1], then fill it left to right.
i = 1 (pair [2,3]): check j = 0 (pair [1,2]). Is pairs[0][1] < pairs[1][0], that is 2 < 2? No, the endpoints touch but the chain needs a strict gap. So dp[1] stays 1.
i = 2 (pair [3,4]): check j = 0 (pair [1,2]). Is 2 < 3? Yes, so dp[2] = max(1, dp[0] + 1) = 2. Then check j = 1 (pair [2,3]). Is 3 < 3? No. So dp[2] stays 2.
The longest chain ending at index 2 has length 2, formed by [1,2] -> [3,4]. The answer is max(dp) = 2.
Code
- Time Complexity: O(n^2). Sorting takes O(n log n). The nested DP loop runs in O(n^2). The dominant term is O(n^2).
- Space Complexity: O(n). The
dparray uses O(n) space.
The nested loop computes the best chain ending at every individual pair, but the problem only asks for the overall maximum length. Because this is the activity selection problem, a greedy choice removes that extra work and brings the running time down to O(n log n).
Approach 2: Greedy (Sort by End)
Intuition
The greedy strategy for activity selection is to sort the intervals by their end value, then scan left to right and pick each interval whose start comes after the end of the last interval picked. Picking the pair that ends earliest leaves the most room on the number line for the remaining pairs, which is why it never hurts to take it.
The proof is an exchange argument. Suppose some optimal chain does not begin with the pair that ends earliest. Call that earliest-ending pair P', and call the first pair the optimal chain uses P. Since P' ends no later than P, swapping P' in for P keeps every later pair valid (they still start after the new, earlier end). The swapped chain has the same length, so an optimal chain that starts with P' exists. Applying the same argument to the rest of the chain shows the greedy choice is safe at every step.
Algorithm
- Sort
pairsby the second element (end value). - Initialize
chainEndto negative infinity andcount = 0. - Iterate through the sorted pairs. For each pair
[a, b]: - If
a > chainEnd, this pair can extend the chain. Incrementcountand setchainEnd = b. - Return
count.
Example Walkthrough
Code
- Time Complexity: O(n log n). Sorting takes O(n log n). The single pass through the sorted array is O(n). Total: O(n log n).
- Space Complexity: O(1). We only use a few integer variables. The sort is in-place.