Maximum Length Pair Chain
Updated
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[][]) → intExamples
Example 1
pairs = [[3,4],[1,2],[2,3]]return = 2One longest chain is [1,2] -> [3,4]. The pair [2,3] cannot come right after [1,2], because the next pair must start strictly after the previous pair ends, and here the two values are equal. No order of all three pairs works, so the answer is two.
Example 2
pairs = [[-10,-5],[-4,0],[1,2]]return = 3Each pair ends before the next one starts, so all three pairs form a valid chain in the order shown. The answer is three.
Example 3
pairs = [[-1000000000,-999999999],[999999998,1000000000]]return = 2The first pair ends far below where the second pair starts, so the second pair can follow the first. Both pairs fit in one chain, and the answer is two.
Constraints
1 <= pairs.length <= 1000- Every
pairs[i]has exactly two integers. -10^9 <= pairs[i][0] < pairs[i][1] <= 10^9
More Amazon Onsite Interview questions
- LRU Cache for Query ResultsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Maximal SquareONSITE INTERVIEW · Seen Nov 2026
- Serialize and Deserialize a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course Schedule IIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Diagonal Traversal of a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Spread Through a GridPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Optimal Account BalancingONSITE INTERVIEW · Seen Nov 2026
- Task SchedulerOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Number of IslandsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Maximum Length Pair ChainInMobi · ONSITE INTERVIEWInMobi interview questions
- Tennis Court SchedulingAtlassian · PHONE SCREEN · ONSITE INTERVIEWAtlassian interview questions
- Minimum Station Tracks for a Train ScheduleBNSF Railway · ONSITE INTERVIEWBNSF Railway interview questions
- Best Time to Buy and Sell Stock IIKotak Mahindra Bank · ONSITE INTERVIEWKotak Mahindra Bank interview questions
- Unit-Weight Knapsack with Limited QuantitiesGoogle · ONSITE INTERVIEWGoogle interview questions
- Reduce Array Size to At Most HalfMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Maximize Monsters DefeatedSalesforce · ONSITE INTERVIEWSalesforce interview questions
- Maximize Workday EarningsCitadel · OA · PHONE SCREEN · ONSITE INTERVIEWCitadel interview questions
- Jump Game IIOracle · ONSITE INTERVIEWOracle interview questions
- Minimum Removals for Non-Overlapping IntervalsByteDance · PHONE SCREEN · ONSITE INTERVIEWByteDance interview questions
Amazon interview experiences
- Amazon Experienced SDE Onsite Questions: 1 Experience
- Amazon SDE Onsite Interview Questions: 9 Experiences
- Amazon SDE II and L5 FDE Interview Questions: 4 Experiences
- Amazon Full-Time OA Problems, Earlier Reports (Part 5 of 5)
- Amazon Full-Time OA Problems, Recent Reports (Part 4 of 5)
- Amazon New Grad OA Problems: Every Task We Have (Part 3 of 5)