Two Best Non-Overlapping Events solution and explanation
Google
9 more videos on this problem
Two Best Non Overlapping Events | Leetcode 2054Techdose · 22:27 · 9K views
2054. Two Best Non-Overlapping Events | Knapsack DP | Line Sweep + Greedy | 3 ApproachesAryan Mittal · 23:09 · 4K views
2054. Two Best Non-Overlapping Events | LEETCODE BIWEEKLY CONTEST 64 | LEETCODEcode Explainer · 12:24 · 3K views
2054. Two Best Non-Overlapping Events (Leetcode Medium)Programming Live with Larry · 12:12 · 1K views
Разбор задачи LeetCode 2054. Two Best Non-Overlapping Events @algoseekeeViktor Karpov · 1:46:36 · 1K views
2054. Two Best Non-Overlapping Events | Leetcode Daily - PythonLeetcode Daily · 10:27 · 796 views
Daily Leetcode #2093: Dec 23, 2025 - 2054. Two Best Non-Overlapping EventsProgramming Live with Larry · 8:56 · 592 views
LeetCode 2054 Two Best Non Overlapping Events | Binary Search | Greedy | Razorpay Interview QuestionCode Harmony · 18:45 · 592 views
Leetcode 2054. Two Best Non-Overlapping EventsElite Code · 34:18 · 545 views
Two Best Non Overlapping Events | LeetCode 2054 - Pythonimpoldev · 9:57 · 276 views
The problem
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:
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 <= 105events[i].length == 31 <= startTimei <= endTimei <= 1091 <= 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.
def maxTwoEvents(events):
events.sort(key=lambda x: x[1])
n = len(events)
max_values = [0] * n
max_val = 0
res = 0
for i in range(n - 1, -1, -1):
start, end, value = events[i]
max_val = max(max_val, value)
max_values[i] = max_val
def find_next(idx):
low, high = 0, idx
while low < high:
mid = (low + high) // 2
if events[mid][1] < events[idx][0]:
low = mid + 1
else:
high = mid
return low
for i in range(n):
start, end, value = events[i]
next_index = find_next(i+1)
max_remaining_value = max_values[next_index] if next_index < n else 0
res = max(res, value + max_remaining_value)
return resimport java.util.*;
class Solution {
public int maxTwoEvents(int[][] events) {
Arrays.sort(events, (a, b) -> a[1] - b[1]);
int n = events.length;
int[] maxValues = new int[n];
int maxVal = 0;
int res = 0;
for (int i = n - 1; i >= 0; i--) {
maxVal = Math.max(maxVal, events[i][2]);
maxValues[i] = maxVal;
}
for (int i = 0; i < n; i++) {
int nextIndex = binarySearch(events, i + 1, events[i][1]);
int maxRemainingValue = nextIndex < n ? maxValues[nextIndex] : 0;
res = Math.max(res, events[i][2] + maxRemainingValue);
}
return res;
}
private int binarySearch(int[][] events, int start, int target) {
int low = 0, high = start;
while (low < high) {
int mid = (low + high) / 2;
if (events[mid][1] < target) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
}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.
Time Complexity: O(n log n) due to sorting and binary search.
Space Complexity: O(n) for storing maximum values array.
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.
function maxTwoEvents(events) {
events.sort((a, b) => a[1] - b[1]);
const n = events.length;
let maxVal = 0;
const maxValues = new Array(n).fill(0);
let result = 0;
for (let i = n - 1; i >= 0; i--) {
maxVal = Math.max(maxVal, events[i][2]);
maxValues[i] = maxVal;
}
for (let i = 0; i < n; i++) {
const nextIndex = binarySearch(events, events[i][1] + 1);
const maxRemainingValue = nextIndex < n ? maxValues[nextIndex] : 0;
result = Math.max(result, events[i][2] + maxRemainingValue);
}
return result;
function binarySearch(events, start) {
let low = 0, high = events.length;
while (low < high) {
const mid = Math.floor((low + high) / 2);
if (events[mid][0] < start) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
}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.
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.
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.
class Solution {
public:
int maxTwoEvents(vector<vector<int>>& events) {
ranges::sort(events);
int n = events.size();
vector<int> f(n + 1);
for (int i = n - 1; ~i; --i) {
f[i] = max(f[i + 1], events[i][2]);
}
int ans = 0;
for (const auto& e : events) {
int v = e[2];
int left = 0, right = n;
while (left < right) {
int mid = (left + right) >> 1;
if (events[mid][0] > e[1]) {
right = mid;
} else {
left = mid + 1;
}
}
if (left < n) {
v += f[left];
}
ans = max(ans, v);
}
return ans;
}
};function maxTwoEvents(events: number[][]): number {
events.sort((a, b) => a[0] - b[0]);
const n = events.length;
const f: number[] = Array(n + 1).fill(0);
for (let i = n - 1; ~i; --i) {
f[i] = Math.max(f[i + 1], events[i][2]);
}
let ans = 0;
for (const [_, end, v] of events) {
let [left, right] = [0, n];
while (left < right) {
const mid = (left + right) >> 1;
if (events[mid][0] > end) {
right = mid;
} else {
left = mid + 1;
}
}
const t = left < n ? f[left] : 0;
ans = Math.max(ans, t + v);
}
return ans;
}func maxTwoEvents(events [][]int) int {
sort.Slice(events, func(i, j int) bool {
return events[i][0] < events[j][0]
})
n := len(events)
f := make([]int, n+1)
for i := n - 1; i >= 0; i-- {
f[i] = max(f[i+1], events[i][2])
}
ans := 0
for _, e := range events {
v := e[2]
left, right := 0, n
for left < right {
mid := (left + right) >> 1
if events[mid][0] > e[1] {
right = mid
} else {
left = mid + 1
}
}
if left < n {
v += f[left]
}
ans = max(ans, v)
}
return ans
}impl Solution {
pub fn max_two_events(mut events: Vec<Vec<i32>>) -> i32 {
events.sort_by(|a, b| a[0].cmp(&b[0]));
let n: usize = events.len();
let mut f: Vec<i32> = vec![0; n + 1];
for i in (0..n).rev() {
f[i] = f[i + 1].max(events[i][2]);
}
let mut ans: i32 = 0;
for e in &events {
let mut v: i32 = e[2];
let mut left: usize = 0;
let mut right: usize = n;
while left < right {
let mid = (left + right) >> 1;
if events[mid][0] > e[1] {
right = mid;
} else {
left = mid + 1;
}
}
if left < n {
v += f[left];
}
ans = ans.max(v);
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sorting and Binary Search | Time Complexity: O(n log n) due to sorting and binary search. |
| Dynamic Programming with Two Pass | Time Complexity: O(n log n), consisting mainly of the sorting and series of binary searches. |
| Sorting + Binary Search | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting + Binary Search | O(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. |
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.