Abstract / Summary

Given a list of intervals, remove those completely covered by another and count how many remain.

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).

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 receives a collection of integer intervals and returns the count of intervals that are not completely covered by any other interval in the collection. The algorithm relies on a min-heap to process intervals in a deterministic order, while a single variable tracks the farthest right endpoint seen so far. Each time an interval extends beyond this tracked endpoint, it is counted as uncovered and the tracker is updated.

Key Steps

Building the priority queue

todo = []
for a, b in intervals:
    heappush(todo, (a, -b))   # sort by start (ascending), then end (descending)

The loop iterates over the input list, inserting each interval into a heap. By storing the start coordinate as the first element and the negated end coordinate as the second, the heap yields intervals ordered first by increasing start value and, for equal starts, by decreasing end value. This ordering guarantees that longer intervals with the same left boundary appear before shorter ones.

Scanning the sorted intervals

covered = 0   # end of already covered interval
while todo:
    a, b = heappop(todo)
    b = -b   # restore original end value
    if b > covered:
        result += 1
        covered = b

The loop extracts intervals one by one from the heap. After restoring the original end coordinate, the algorithm compares it with the current covered value. If the interval’s end exceeds covered, the interval cannot be fully contained within any previously processed interval, so the result counter is incremented and covered is updated to this new farthest endpoint. When the end does not exceed covered, the interval is entirely nested inside a previously seen interval and is therefore ignored.

Returning the final count

return result

After the heap is exhausted, the method returns the accumulated count of uncovered intervals.

Edge Cases Handled

When multiple intervals share the same start point, the negated end ensures that the longest interval is examined first. Consequently, any shorter interval that begins at the same position will have an end that does not exceed the current covered value and will be correctly identified as covered.

If the input list is empty, the initial heap remains empty, the while-loop body never executes, and the method returns 0, which is the appropriate count for an empty collection.

Intervals that are identical in both start and end coordinates are treated as covering each other; the first occurrence updates covered, while subsequent identical intervals fail the b > covered test and are not counted.

Intervals presented in arbitrary order are normalized by the heap insertion, so the algorithm does not depend on any pre-existing ordering of the input.

Performance Optimizations

The use of a heap eliminates the need for a separate sorting pass; each interval is inserted with heappush, and the ordering is maintained incrementally. By encoding the end coordinate as a negative value, the algorithm achieves a descending order on the second key without additional data structures or custom comparator logic.

The algorithm maintains only a constant amount of auxiliary state (result, covered, and the heap itself), avoiding the allocation of auxiliary arrays or maps. The single pass through the heap after construction ensures that each interval is examined exactly once, minimizing overhead.

Overall, the design leverages the heap’s logarithmic insertion and extraction costs while keeping the per-interval work minimal, resulting in an efficient solution for the problem of counting non-covered intervals.

Imagine you have a big pile of colorful ribbons on the floor. Each ribbon starts at one spot and ends at another spot. Some ribbons are long and some are short. Some ribbons might be hiding completely underneath long ones. The goal is to count how many ribbons are visible.

First, the code organizes all the ribbons by looking at their starting spots. If two ribbons start at the exact same place, it puts the longest one first so it can be seen easily.

Then, there is a special box called a counter that starts at zero. A helper variable keeps track of the furthest end point seen so far. As the code looks at each ribbon, it checks if that ribbon stretches past the end of the ones already placed. If the ribbon reaches out further than everything else, it means a new piece of the ribbon is visible. Every time a new piece is found, the count goes up by one, and the helper remembers this new furthest end point. Once every ribbon has been checked, the final count tells how many unique, uncoverable ribbons were in the pile.

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	JS	Java			Go	TS
	Progiez	C++	Python		Java
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fartem						Ruby
	fpdjsns	C++
	fsq	C++
	JoshCrozier			JS
	keineahnung2345	C++
	lkwq007		Python
	suxrobGM					C#
	trung-hn		Python
	varunu28				Java
	wisdompeak	C++
	withaarzoo	C++
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, TypeScript
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fpdjsns	C++
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
suxrobGM	C#
trung-hn	Python
varunu28	Java
wisdompeak	C++
withaarzoo	C++
YuriSpiridonov	Python

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