Abstract / Summary

Given pairs of numbers pick as many as possible so each next pair starts after the previous one ends and find the largest count.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 62% (500k+ submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming
• Greedy
• Sorting

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a method that computes the maximum length of a chain that can be formed from a collection of integer pairs. A chain is valid when the first element of each subsequent pair is strictly greater than the second element of the preceding pair. The algorithm follows a greedy strategy that repeatedly selects the pair with the smallest possible second element that still satisfies the ordering constraint. By iterating until no further pair can be added, the method returns the length of the longest achievable chain.

Core Logic

The algorithm initializes three control variables:

length = 0
current = -1001
again = True

length tracks the number of pairs included in the chain, current holds the second element of the most recently chosen pair, and again signals whether another iteration of the outer loop should be performed.

The outer loop continues while again remains true:

while again:
    next = +1001
    again = False
    ...

Inside each iteration, next is set to a large positive sentinel value. The flag again is cleared, and the inner loop scans every pair in the input list:

for p in pairs:
    if p[0] > current and p[1] < next:
        next = p[1]
        again = True

The condition p[0] > current enforces the strict ordering requirement, while p[1] < next ensures that among all qualifying pairs the one with the smallest second element is chosen. When such a pair is found, next is updated to its second element and again is set to true, indicating that the chain can be extended.

After the inner loop finishes, the algorithm checks whether a suitable pair was identified:

if again:
    current = next
    length += 1

If so, current is advanced to the selected pair’s second element and the chain length counter is incremented. When no qualifying pair exists, again stays false, the outer loop terminates, and the final chain length is returned:

return length

Edge Cases Handled

The method gracefully handles an empty input list. With no pairs to examine, the inner loop never sets again to true, causing the outer loop to exit after the first pass and returning a length of zero.

Pairs whose first element is not greater than the current bound are automatically excluded by the p[0] > current test, ensuring that only strictly increasing sequences are considered. The algorithm also correctly processes inputs containing duplicate pairs; each duplicate is evaluated independently, but only one can be selected per iteration because the selection criterion depends on the smallest second element.

When multiple pairs satisfy the ordering constraint in a given iteration, the algorithm’s p[1] < next check guarantees that the pair with the minimal ending value is chosen. This behavior aligns with the greedy principle that selecting the earliest finishing interval leaves the greatest room for subsequent selections.

The sentinel values -1001 for current and +1001 for next act as lower and upper bounds respectively. They allow the first iteration to consider any pair whose first element exceeds -1001, effectively treating the start of the chain as an unrestricted point. Likewise, the large positive sentinel ensures that any qualifying pair will replace next on the first match.

Implicit Performance Optimizations

The implementation avoids any explicit sorting of the input list. By repeatedly scanning the list and selecting the minimal feasible endpoint, it achieves the effect of an ordered traversal without the overhead of a sort operation. This approach reduces auxiliary memory usage because no additional data structures are allocated beyond a few scalar variables.

The use of a boolean flag (again) to control the outer loop eliminates the need for a separate counter or index to detect termination. The flag is set only when a new pair is incorporated, allowing the loop to stop immediately once the chain cannot be extended further.

Because the algorithm updates only scalar values (current, next, length) and reuses the same loop variables across iterations, it maintains a low constant factor in its execution. The inner loop’s simple conditional check (p[0] > current and p[1] < next) is inexpensive, contributing to efficient per-iteration processing.

Overall, the method delivers a concise greedy solution that leverages sentinel values and minimal state to compute the longest possible chain from the given pairs.

Imagine you have a big pile of cards, and each card has two numbers written on it. You want to build the longest train of cards possible. To add a card to the train, the first number on the new card must be bigger than the second number on the card you just placed down.

The computer starts by looking for the card that ends with the smallest number. It picks that one first because it leaves as much room as possible for more cards to be added later. The computer keeps searching through the pile over and over again to find the next best card that fits perfectly onto the end of the chain. Every time it finds a card that fits, the chain grows by one. The computer keeps going like this until it reaches a point where no more cards can be added to the train. Once there are no cards left that can fit, the building is finished.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python						TS
	WalkCCC	C++	Java	Python
	leetcode.ca	C++	Java	Python		Rust			Go	TS
	LeetcodeHelp	C++	Java	Python
	Progiez	C++	Java	Python
github	black-shadows	C++
	charles-wangkai		Java
	everthis				JS
	gouthampradhan		Java
	JoshCrozier				JS
	linouk23	C++
	lkwq007			Python
	MacJim	C++
	ruoru					Rust
	suxrobGM						C#
	trung-hn			Python
	varunu28		Java
	vli02							C
	wisdompeak	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
gouthampradhan	Java
JoshCrozier	JavaScript
linouk23	C++
lkwq007	Python
MacJim	C++
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
wisdompeak	C++
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality