FastPrep
Problem · Array

Maximum Length Pair Chain

Learn this problem
● MediumInMobi logoInMobiFULLTIMEONSITE INTERVIEW

Problem statement

You are given an array pairs, where every pair is [start, end] and start < end.

A pair [c, d] may follow [a, b] in a chain only when b < c. You may choose each pair at most once, may leave pairs unused, and may arrange chosen pairs in any order.

Return the maximum possible number of pairs in a valid chain.

Function

maxPairChainLength(pairs: int[][]) → int

Examples

Example 1

pairs = [[3,4],[1,2],[2,3]]return = 2

One maximum chain is [1,2] -> [3,4]. The pair [2,3] cannot immediately follow [1,2] because the inequality is strict.

Example 2

pairs = [[-10,-5],[-4,0],[1,2]]return = 3

All three pairs form a valid chain in their displayed order.

Constraints

  • 1 <= pairs.length <= 1000
  • Every pairs[i] has exactly two integers.
  • -10^9 <= pairs[i][0] < pairs[i][1] <= 10^9

More InMobi problems

drafts saved locally
public int maxPairChainLength(int[][] pairs) {
    // write your code here
}
pairs[[3,4],[1,2],[2,3]]
expected2
checking account