Abstract / Summary

Given a list of intervals, find for each interval the index of the next interval that starts at or after its end.

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 56% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• 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, for each interval in a collection, determines the index of the interval whose start point is the smallest value that is not less than the current interval’s end point. If such an interval does not exist, the method records -1. The result is returned as a vector whose length matches the input size, preserving the original order of intervals.

Data Preparation

The first phase constructs an ordered associative container that maps each interval’s start value to its original position. By iterating over the input vector and inserting (start, index) pairs into a map, the code creates a structure that automatically keeps the keys sorted.

map<int, int> sorted;
for (int i = 0; i < intervals.size(); i++)
{
    auto start = intervals[i][0];
    sorted[start] = i;
}

Because map maintains a strict weak ordering of its keys, later look-ups can efficiently locate the smallest start that satisfies a given bound.

Query Phase

The second phase walks through the original intervals, extracts the start and end of each, and uses the previously built map to locate the right interval. The lower_bound operation on the map returns an iterator to the first element whose key is not less than the queried end value.

vector<int> result;
result.reserve(intervals.size());
for (auto& i : intervals)
{
    auto start = i[0];
    auto end   = i[1];

    auto pos = sorted.lower_bound(end);
    if (pos == sorted.end())
        result.push_back(-1);
    else
        result.push_back(pos->second);
}
return result;

If lower_bound reaches the end of the map, it indicates that no interval starts at or after the current end, and -1 is recorded. Otherwise, the index stored in the map entry is appended to the result.

Edge Cases Handled

When an interval’s end exceeds all start values in the collection, the lower_bound call yields sorted.end(). The conditional branch captures this situation and inserts -1, ensuring that the output correctly reflects the absence of a suitable right interval.

If multiple intervals share the same start value, the map stores the last index encountered for that start because later insertions overwrite earlier ones. This deterministic choice guarantees that the method always returns a single, well-defined index for any given start value.

The algorithm also gracefully handles an empty input vector: the initial loop does not execute, the result vector remains empty, and the method returns an empty vector without error.

Performance Optimizations

The code reserves space in the result vector equal to the number of intervals before populating it. This pre-allocation eliminates repeated reallocations and copies as elements are appended, yielding a smoother memory usage pattern.

Using a map provides logarithmic-time search for the lower bound of each interval’s end, which is more efficient than a linear scan over unsorted starts.

The range-based for loop iterates by reference (auto& i), avoiding unnecessary copies of the inner vectors while still allowing direct access to their elements.

Type deduction with auto reduces verbosity and lets the compiler infer the most appropriate types, potentially enabling better register allocation and inlining.

Overall, the combination of ordered storage, pre-allocation, and reference-based iteration contributes to a solution that scales well with the size of the input while keeping the runtime overhead minimal.

Imagine a row of colorful bridges. Some bridges start at a certain distance and end a little bit further away. This code is like playing a game where you stand at the end of one bridge and try to find the very next bridge that starts at the same spot or even further down the path.

First, the computer gathers all the starting points of the bridges and puts them into a special list that is kept organized from smallest to largest, just like sorting your blocks by size. This makes it really fast to peek at them later.

Next, the computer looks at each bridge one by one. It finds where the bridge ends and then looks through that organized list to see if there is another bridge that begins right there or a little bit further ahead. If it finds one, it writes down which bridge that is. If it reaches the very end of the line and realizes there are no more bridges left to jump onto, it writes down a special number to say that nothing was found. It keeps doing this until it has checked every single bridge in the whole set.

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

Time: loglinear
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++	Python		Java					TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java				Go	TS
	LeetcodeHelp	C++	Python		Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python		Java
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fengvyi	C++
	fsq	C++
	halfrost								Go
	JoshCrozier			JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007		Python
	MacJim	C++
	ruoru						Rust
	sonugiri1043	C++
	suxrobGM					C#
	trung-hn		Python
	varunu28				Java
	XiaotaoGuo	C++
	yuanliu666							Kotlin
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fengvyi	C++
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
MacJim	C++
ruoru	Rust
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
XiaotaoGuo	C++
yuanliu666	Kotlin
YuriSpiridonov	Python
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