315. Maximum Length Chain of Pairs

Given n pairs of integers (a, b) with a < b, a pair (c, d) can follow a pair (a, b) in a chain if b < c. Find the length of the longest chain that can be formed by picking a subset of the given pairs and arranging them in a valid chain.

Input: The first line contains n. Each of the next n lines contains a pair of integers a and b (a < b). Output: Print a single integer - the length of the longest chain of pairs.

1 <= n <= 10^4

Sorting by the FIRST element (not the second) before applying the LIS-style DP is what guarantees any valid chain appears in increasing order within the sorted list, making the subsequent DP correct.

Find the longest chain of pairs where each pair's second value is less than the next pair's first value. Brute force: Try every possible subset of pairs and check if they form a valid chain in some order - this is exponential (2^n subsets), impractical for n up to 10^4. Optimised: This is structurally IDENTICAL to Longest Increasing Subsequence - sorting first establishes a valid processing order, and the DP recurrence just swaps LIS's 'value less than' compatibility test for this problem's 'second element less than first element' test, reusing the exact same O(n²) (or O(n log n) with binary search) technique.

Enumerate every one of the 2^n subsets of the given pairs, and for each subset, try every ordering (or simply sort it by first element) and check whether consecutive pairs in that order satisfy the chaining condition (previous pair's second element less than the next pair's first element); keep track of the largest valid chain length found across all subsets. This checks the definition exhaustively at combinatorial cost. Time: O(2^n * n log n) Space: O(n)

Sort the pairs by their second element (b) ascending in O(n log n). Then scan through them once, greedily selecting a pair into the chain whenever its first element (a) is strictly greater than the second element (b) of the last pair selected, and updating the 'last selected' pair to this one. This greedy choice is optimal because always keeping the smallest possible 'end' value at each chain length leaves the most room for future pairs, letting the whole answer be computed in a single linear pass after sorting. Time: O(n log n) Space: O(1) extra

Sort the pairs by their first element (a) in O(n log n). Define dp[i] as the length of the longest valid chain ending with pair i, computed as 1 plus the maximum dp[j] over all j < i whose second element (b) is less than pair i's first element (a); if no such j exists, dp[i] = 1. This is exactly the longest-increasing-subsequence recurrence applied to the chaining condition, evaluated with a nested loop over all prior pairs for each pair. Time: O(n^2) Space: O(n)

1. Sort the pairs by their FIRST element, so any valid chain appears in increasing order in the sorted list. 2. dp[i] = length of the longest chain ENDING with pair i; dp[i] = 1 + max(dp[j]) over every j<i whose second element is less than pair i's first element. 3. The answer is the maximum value anywhere in the dp array - this is the SAME shape of problem as Longest Increasing Subsequence, just with a different 'compatible predecessor' test.

Time: O(n²) for the straightforward DP (matching LIS's complexity); O(n log n) with a similar tails-array optimization as LIS. Space: O(n), for the dp array and the sorted pairs.

Test n = 1 (chain length 1), a set of pairs that all mutually overlap (chain length 1), and n = 10^4 (upper bound), which favors sorting plus an O(n log n)/O(n^2) DP over brute force.

Be ready to explicitly recognize and state this as 'LIS with a custom compatibility test' - this pattern-matching insight immediately unlocks both the O(n²) and the faster O(n log n) techniques from LIS, without needing to derive anything from scratch.