Skip to main content
Talentd

Two Best Non-Overlapping Events - Solution & Explanation

MediumArrayBinary SearchDynamic ProgrammingSorting14 min readAsked at: Amazon, Microsoft, Meta +4
Practice this problem

Problem Statement

You are given a 0-indexed 2D integer array of events where events[i] = [startTimei, endTimei, valuei]. The ith event starts at startTimei and ends at endTimei, and if you attend this event, you will receive a value of valuei. You can choose at most two non-overlapping events to attend such that the sum of their values is maximized.

Return this maximum sum.

Note that the start time and end time is inclusive: that is, you cannot attend two events where one of them starts and the other ends at the same time. More specifically, if you attend an event with end time t, the next event must start at or after t + 1.

 

Example 1:

Input: events = [[1,3,2],[4,5,2],[2,4,3]]
Output: 4
Explanation: Choose the green events, 0 and 1 for a sum of 2 + 2 = 4.

Example 2:

Example 1 Diagram 
Input: events = [[1,3,2],[4,5,2],[1,5,5]]
Output: 5
Explanation: Choose event 2 for a sum of 5.

Example 3:

Input: events = [[1,5,3],[1,5,1],[6,6,5]]
Output: 8
Explanation: Choose events 0 and 2 for a sum of 3 + 5 = 8.

 

Constraints:

  • 2 <= events.length <= 105
  • events[i].length == 3
  • 1 <= startTimei <= endTimei <= 109
  • 1 <= valuei <= 106

Approach Overview

Problem Overview: You are given a list of events where each event has a start time, end time, and value. The goal is to attend at most two non-overlapping events such that the total value is maximized. Two events overlap if one starts before the other ends.

Approach 1: Sorting and Binary Search (O(n log n) time, O(n) space)

Sort events by start time. For each event, you want to quickly find the next event that starts strictly after its end time. Binary search makes this possible. First, preprocess the events and build a suffix array where suffixMax[i] stores the maximum value obtainable from any event starting at or after index i. Then iterate through each event and use binary search to locate the first event whose start time is greater than the current event's end. Combine the current event’s value with the best value from the suffix array. The key insight: sorting enables efficient lookups of the next valid event. Time complexity is O(n log n) due to sorting and binary search per event, while space complexity is O(n) for the suffix maximum array.

This approach relies heavily on sorting and indexed lookups over an array. It performs well even when the event list is large because each lookup avoids scanning the remaining events linearly.

Approach 2: Dynamic Programming with Two Pass (O(n log n) time, O(n) space)

This method separates the problem into two directional passes. First, sort events by start time. During the forward pass, compute the best value achievable starting from each position. During the backward pass, evaluate each event as the first event and determine the best compatible second event. Instead of recomputing values repeatedly, maintain a DP structure that tracks the maximum value seen so far. The idea is similar to building prefix and suffix best values, which avoids recomputation.

Binary search is still used to locate the next valid event after the current one, but the DP structure simplifies how results are combined. The algorithm effectively transforms the problem into two subproblems: selecting the first event and then quickly retrieving the best second event. Sorting dominates the runtime, giving O(n log n) time and O(n) space.

Recommended for interviews: The sorting + binary search solution is the most commonly expected answer. It clearly demonstrates understanding of interval problems, efficient lookups, and preprocessing with suffix maximums. Interviewers usually look for the insight that sorting events allows you to locate the next compatible event in log n time instead of scanning linearly.

Approach 1: Sorting and Binary Search

To maximize the sum of two non-overlapping events, the first step is to sort all events by their end time. With the events sorted, we can iterate through each event and use binary search to find a non-overlapping event with the maximum possible value that starts after the current event ends. This approach allows efficient selection of the second event by leveraging the sorted order.

This solution sorts the events by their end times. It iterates through the events in reverse to keep track of the maximum possible value for the remaining events. A backwards pass through events captures this when we calculate potential non-overlapping pair sums.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n log n) due to sorting and binary search.
Space Complexity: O(n) for storing maximum values array.

Try this approach in the editor →

Approach 2: Dynamic Programming with Two Pass

This approach uses a dynamic programming-inspired method to solve the problem. It involves a first pass to determine the maximum value from a single event up to each point and a second pass to calculate the maximum possible two-event combination utilizing non-overlapping constraints.

This JavaScript implementation similarly sorts the events array by ending times. It then employs a backward traversal to build up the accessible maximum values for later reference. During a subsequent forward traversal, each event is paired with a succeeding non-overlapping event using binary search methods, maximizing the resultant sums progressively.

Code

JavaScript

JavaScript

Complexity

Time Complexity: O(n log n), consisting mainly of the sorting and series of binary searches.
Space Complexity: O(n) due to the need for auxiliary storage of maximum values.

Try this approach in the editor →

Approach 3: Sorting + Binary Search

We can sort the events by their start times, and then preprocess the maximum value starting from each event, i.e., f[i] represents the maximum value of choosing one event from the i-th event to the last event.

Then we enumerate each event. For each event, we use binary search to find the first event whose start time is greater than the end time of the current event, denoted as idx. The maximum value starting from the current event is f[idx] plus the value of the current event, which is the maximum value that can be obtained by choosing the current event as the first event. We take the maximum value among all these values.

The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the number of events.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sorting and Binary Search

Time Complexity: O(n log n) due to sorting and binary search.
Space Complexity: O(n) for storing maximum values array.

Dynamic Programming with Two Pass

Time Complexity: O(n log n), consisting mainly of the sorting and series of binary searches.
Space Complexity: O(n) due to the need for auxiliary storage of maximum values.

Sorting + Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting + Binary SearchO(n log n)O(n)Best general solution. Efficient lookup for the next non-overlapping event after sorting.
Dynamic Programming (Two Pass)O(n log n)O(n)Useful when structuring the solution as prefix/suffix maximum values using DP.

Video Solution

Two Best Non Overlapping Events | Leetcode 2054 • Techdose • 9,737 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Two Best Non-Overlapping Events easy or hard?
Two Best Non-Overlapping Events is typically rated Medium difficulty. The challenge comes from recognizing that sorting and binary search allow efficient pairing of events without checking every combination.
How to solve Two Best Non-Overlapping Events in O(n)?
Pure O(n) is generally not achievable because the events must be sorted by start time or end time to efficiently detect non-overlapping intervals. After sorting, the remaining processing can be linear with auxiliary arrays, but the sorting step keeps the total complexity at O(n log n).
What is the best approach for Two Best Non-Overlapping Events?
The most efficient approach sorts events by start time and uses binary search to locate the next event that begins after the current one ends. A suffix maximum array tracks the best value obtainable from later events. This reduces the search for the second event from O(n) to O(log n), resulting in O(n log n) total time.
What data structure is used in Two Best Non-Overlapping Events?
The solution primarily uses arrays along with sorting and binary search. Many implementations also maintain a suffix maximum array to quickly retrieve the best value among future events. Some variations use heaps (priority queues), but binary search over sorted events is the most common technique.
What is the time complexity of Two Best Non-Overlapping Events?
The optimal solution runs in O(n log n) time. Sorting the events requires O(n log n), and each event performs a binary search to find the next non-overlapping event in O(log n). Space complexity is O(n) for storing suffix maximum values or dynamic programming states.
Two Best Non-Overlapping Events Python or Java solution approach?
In Python or Java, sort the events by start time and build a suffix maximum array of event values. For each event, perform a binary search to find the first event whose start time is greater than the current event's end time, then combine their values to update the maximum result. The overall complexity remains O(n log n).
Is Two Best Non-Overlapping Events asked at Google, Amazon, or Meta?
Interval scheduling and event selection problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variations involving overlapping intervals, scheduling optimization, and maximum profit selection are common. This problem tests sorting, binary search, and dynamic programming skills.

Ready to solve this problem?

Practice Two Best Non-Overlapping Events with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximize Win From Two Segments

Next

Maximum Number of Events That Can Be Attended II