Two Best Non-Overlapping Events — Problem & Solution
Two Best Non-Overlapping Events solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Two Best Non-Overlapping Events is a medium coding problem on arrays, dynamic programming and sorting, asked in Amazon, Google and Razorpay interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Sorting, Binary Search
- Asked at: Amazon, Google, Razorpay
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Each events[i] = [startTime, endTime, value] is an event you may attend from startTime to endTime, both inclusive, earning value.
You may attend at most two events, and they must not overlap: because times are inclusive, the second event has to start strictly after the first one ends (end1 < start2).
Return the maximum total value you can earn.
Example 1
Input: events = [[2,4,6],[5,9,3],[1,2,4],[4,8,5]]
Output: 9
Explanation: [1,2,4] with [4,8,5], or [2,4,6] with [5,9,3]. [1,2,4] and [2,4,6] overlap at time 2.
Example 2
Input: events = [[1,3,2],[4,5,2],[1,5,5]]
Output: 5
Explanation: A single event can be the best choice.
Example 3
Input: events = [[1,5,3],[1,5,1],[6,6,5]]
Output: 8
Constraints
2 <= events.length <= 10^5events[i].length == 31 <= startTime <= endTime <= 10^91 <= value <= 10^6
Hints for Two Best Non-Overlapping Events
Hint 1
Fix the earlier of the two events. The best partner is the most valuable event that starts after it ends.
Hint 2
Sort events by start time and precompute a suffix maximum of values.
Hint 3
For each event, binary-search the first event whose start is greater than this event's end; add the suffix maximum from there (or nothing).
How to solve Two Best Non-Overlapping Events
Pair each event with the best event that starts strictly after it ends. Sorted by start, the candidates form a suffix, so a suffix-maximum array plus binary search answers each event in O(log n).
Approach
- Sort the events by
startTime. - Build
suffix[i], the maximum value among eventsi..n-1. - For each event, find the first index
jwithstart[j] > endby binary search. - The candidate is
value + suffix[j](justvalueifj == n); return the maximum candidate.
Why it works
In any optimal pair, the earlier event's end is below the later event's start; the later one lies in the suffix found by the binary search, and the suffix maximum is at least its value. Single events are covered by the j == n case or by pairing with nothing, since values are positive and attending one event is allowed.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Times are inclusive: an event ending at 4 and one starting at 4 overlap — search for
start > end, not>=. - Attending a single event is allowed and may be optimal.
- Do not pair an event with itself; the strict inequality already rules it out since
start <= end.
Reference solution
Python
from typing import List
from bisect import bisect_right
def maxTwoEvents(events: List[List[int]]) -> int:
ev = sorted(events)
starts = [e[0] for e in ev]
n = len(ev)
suffix = [0] * (n + 1) # suffix[i]: best value among ev[i:]
for i in range(n - 1, -1, -1):
suffix[i] = max(suffix[i + 1], ev[i][2])
best = 0
for s, e, v in ev:
j = bisect_right(starts, e) # first event starting after e
best = max(best, v + suffix[j])
return bestJava
public static int maxTwoEvents(int[][] events) {
int[][] ev = events.clone();
Arrays.sort(ev, (a, b) -> Integer.compare(a[0], b[0]));
int n = ev.length;
int[] suffix = new int[n + 1]; // suffix[i]: best value among ev[i..]
for (int i = n - 1; i >= 0; i--) suffix[i] = Math.max(suffix[i + 1], ev[i][2]);
int best = 0;
for (int[] e : ev) {
int lo = 0, hi = n; // first event starting after e[1]
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (ev[mid][0] <= e[1]) lo = mid + 1; else hi = mid;
}
best = Math.max(best, e[2] + suffix[lo]);
}
return best;
}C++
int maxTwoEvents(vector<vector<int>>& events) {
vector<vector<int>> ev = events;
sort(ev.begin(), ev.end());
int n = ev.size();
vector<int> suffix(n + 1, 0); // suffix[i]: best value among ev[i..]
for (int i = n - 1; i >= 0; i--) suffix[i] = max(suffix[i + 1], ev[i][2]);
int best = 0;
for (auto& e : ev) {
int lo = 0, hi = n; // first event starting after e[1]
while (lo < hi) {
int mid = (lo + hi) / 2;
if (ev[mid][0] <= e[1]) lo = mid + 1; else hi = mid;
}
best = max(best, e[2] + suffix[lo]);
}
return best;
}JavaScript
var maxTwoEvents = function(events) {
var ev = events.slice().sort(function(a, b) { return a[0] - b[0]; });
var n = ev.length;
var suffix = []; // suffix[i]: best value among ev[i..]
for (var z = 0; z <= n; z++) suffix.push(0);
for (var i = n - 1; i >= 0; i--) suffix[i] = Math.max(suffix[i + 1], ev[i][2]);
var best = 0;
for (var t = 0; t < n; t++) {
var lo = 0, hi = n; // first event starting after ev[t][1]
while (lo < hi) {
var mid = (lo + hi) >> 1;
if (ev[mid][0] <= ev[t][1]) lo = mid + 1; else hi = mid;
}
best = Math.max(best, ev[t][2] + suffix[lo]);
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming