Command Palette

Search for a command to run...

Hectal
Problem 42.6 · Pattern Recognition DrillsMedium

Maximum Length of Pair Chain

What it teaches:

Practise it on judges as “Maximum Length of Pair Chain”.

In plain words

Each pair is like a meeting with a start and an end, and the next one must start after the previous one ends. To fit in as many as possible, always pick the one that finishes earliest: it leaves the most room for the rest. So line them up by end time and take each one that starts after the last one you took.

Return the length of the longest chain. Example: pairs = [[1,2],[7,8],[4,5]] → 3.

The problem

Pair [c, d] can follow [a, b] if b < c. Return the longest chain you can form (pairs in any order).

Example 1

Input: pairs = [[1,2],[7,8],[4,5]]
Output: 3

Constraints

  • 1 ≤ n ≤ 1000

Pattern clues in the wording

  • → Choose the most non-overlapping intervals
  • → Order is free

Stuck? Take one hint at a time

Solution · starter
import java.util.*;

class Solution {
    public int findLongestChain(int[][] pairs) {
        return 0;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#InputExpected
1
pairs = [[1,2],[2,3],[3,4]]
2
2
pairs = [[1,2],[7,8],[4,5]]
3

From slow to fast

Approaches

1. Sort by end, take greedily · O(n log n)
1

Sort by end, take greedily

Time O(n log n) Space O(1) extra

Sort by second value; take a pair whenever its start is after the last taken end.

▶ Dry run: Earliest end firstpairs = [[1,2],[7,8],[4,5]]
[1,2]
0
[4,5]
1
[7,8]
2

state(vars)

end: −∞count: 0

Step 1/4Sorted by end: [1,2], [4,5], [7,8]. Nothing is taken yet.

Approach 1
import java.util.Arrays;

class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> Integer.compare(a[1], b[1]));
        int count = 0;
        long end = Long.MIN_VALUE;
        for (int[] p : pairs) {
            if (p[0] > end) { count++; end = p[1]; }
        }
        return count;
    }
}

Verdict: Optimal by the exchange argument; the LIS-style DP is O(n²).

Before you submit

Edge cases and common mistakes

Test these inputs

  • Touching pairs (b == c can't chain)
  • One pair

Mistakes people make

  • Sorting by start (a long early pair blocks many short ones).

Interview

Follow-up questions

Which course problem is the same idea?