Abstract / Summary

Pick two events that do not overlap and have the highest combined value.

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

Typical patterns to solve this problem:

• Array
• Binary Search
• Dynamic Programming
• Heap (Priority Queue)
• 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 Solution.maxTwoEvents method computes the maximum total value obtainable by attending at most two non-overlapping events. Each event is represented by a triple [start, end, value]. The algorithm iterates through the events in chronological order, maintains a min-heap of ongoing events, and tracks the best single-event value that has already finished. By combining the best finished event with the current one, it derives the optimal pair value.

Key Steps

Sorting the input

for start, end, value in sorted(events):

The events are sorted primarily by their start time (and secondarily by end time and value due to tuple ordering). This ordering guarantees that when processing an event, all earlier-starting events have already been examined, which simplifies the detection of non-overlapping pairs.

Removing already finished events

while finished and finished[0][0] < start:
    endOne, valueOne = heappop(finished)
    one = max(one, valueOne)

The finished heap stores tuples (end, value) for events that have started but not yet been removed. The loop extracts every event whose end time is strictly less than the current event’s start time. Because the heap is ordered by the smallest end time, the condition finished[0][0] < start efficiently identifies all events that cannot overlap with the current one. While extracting, the algorithm updates one to hold the highest value among all events that have already finished.

Combining the best finished event with the current event

result = max(result, one + value)

After the heap cleanup, one represents the maximum value of any event that ends before the current event begins. Adding the current event’s value yields a candidate total for a two-event schedule. result retains the best total seen so far.

Adding the current event to the heap

heappush(finished, (end, value))

The current event is inserted into the finished heap so that it can later serve as a predecessor for subsequent events. The heap continues to store all events that have started but whose end times have not yet been surpassed by later start times.

Final return

return result

When the loop finishes, result contains the maximum sum of values for any two non-overlapping events, or zero if no such pair exists.

Edge Cases Handled

When the input list is empty, the sorted(events) loop never executes, leaving result at its initial value of 0. The method therefore correctly returns 0.

If there is only a single event, the heap will receive that event, but the inner while loop will never pop anything because no later start exists. The combination step computes one + value, where one remains 0, so result becomes the value of that single event. This matches the problem’s requirement of “at most two” events.

Events that share the same start time are processed in order of their end times because of the tuple sort. Since the while condition uses a strict < comparison, events that start at the same time as another’s end are considered non-overlapping, which aligns with the typical inclusive-exclusive interval interpretation.

Events with identical end times are stored together in the heap; the while loop still removes them correctly when a later start exceeds that end time.

Performance Optimizations

The algorithm leverages a min-heap (finished) to keep track of the earliest finishing events. By always popping the smallest end time, it avoids scanning the entire list of active events for each new start, achieving amortized logarithmic update cost.

The variable one stores the maximum value among all events that have already been removed from the heap. Updating one only when an event is popped prevents repeated scans of previously processed events.

Sorting the events once at the beginning provides a deterministic processing order, eliminating the need for additional data structures to locate compatible events later.

Overall, the combination of a single pass through the sorted list, heap-based removal of finished events, and incremental tracking of the best single-event value yields an efficient solution that scales well with the number of events.

Imagine there is a big collection of colorful building blocks spread out on the floor. Each block has a start time, an end time, and a special score written on it. The goal is to pick two blocks that do not overlap in time so that the total score is as high as possible.

The computer looks at all the blocks one by one, starting from the ones that begin the earliest. To keep things organized, it keeps a separate pile of blocks that have already finished their time.

When the computer looks at a new block, it checks the pile to see if any of those old blocks finished before the current one starts. It looks at the scores of those finished blocks and remembers the very best score it has found so far. Then, it adds that best score to the value of the new block. If this combination is bigger than any total it has seen before, it keeps that new total as its new best record. Finally, the computer puts the current block into the pile so it can be considered later when looking at other blocks. By the end, the biggest total that was tracked is the answer.

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	Rust	TS
	Progiez	C++		Python	Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	lkwq007			Python
	Shamik07					Dart
	suxrobGM						C#
	wisdompeak	C++
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
Shamik07	Dart
suxrobGM	C#
wisdompeak	C++
withaarzoo	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