Two Best Non-Overlapping Events
Two Best Non-Overlapping Events is a medium intervals problem solved with the basics pattern.
The best approach, optimal (sort + suffix max + binary search), runs in O(n log n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (check every pair) up.
Problem
You are given a list of events, where events[i] = [start_i, end_i, value_i] describes an event that runs from day start_i to day end_i (both days included) and is worth value_i if you attend it.
You may attend at most two events, and the events you attend must not overlap: if one ends on day t, the other has to start on day t + 1 or later.
Return the largest total value you can collect.
Examples
Example 1
- Input
events = [[1, 2, 4], [3, 5, 3], [2, 6, 5]]- Output
7- Why
- Attend [1, 2] (value 4) and [3, 5] (value 3). The event worth 5 overlaps both others.
Example 2
- Input
events = [[1, 4, 6], [4, 8, 2], [9, 9, 1]]- Output
7- Why
- [1, 4] and [4, 8] share day 4, so they cannot both be chosen. The best pair is 6 + 1.
Example 3
- Input
events = [[1, 10, 9], [2, 3, 4], [5, 6, 4]]- Output
9- Why
- The two short events only add up to 8, so attending the single long event is better.
Constraints
2 <= events.length <= 10^5events[i] = [start_i, end_i, value_i]1 <= start_i <= end_i <= 10^91 <= value_i <= 10^6
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (check every pair) | O(n²) | O(1) |
| Optimal (sort + suffix max + binary search) | O(n log n) | O(n) |
1Brute force (check every pair)
O(n²)All n(n - 1) / 2 pairs are checked.O(1)Only a running maximum.The answer is either one event alone or a pair of events that do not share any day. Try every single event and every pair, and keep the best total.
- best = max value of any single event.
- For every pair i < j, if events[i] ends before events[j] starts or events[j] ends before events[i] starts, update best with their value sum.
- Return best.
class Solution {
public int maxTwoEvents(int[][] events) {
int n = events.length;
int best = 0;
for (int i = 0; i < n; i++) {
best = Math.max(best, events[i][2]);
for (int j = i + 1; j < n; j++) {
if (events[i][1] < events[j][0] || events[j][1] < events[i][0]) {
best = Math.max(best, events[i][2] + events[j][2]);
}
}
}
return best;
}
}class Solution:
def maxTwoEvents(self, events: List[List[int]]) -> int:
n = len(events)
best = 0
for i in range(n):
best = max(best, events[i][2])
for j in range(i + 1, n):
if events[i][1] < events[j][0] or events[j][1] < events[i][0]:
best = max(best, events[i][2] + events[j][2])
return bestclass Solution {
public:
int maxTwoEvents(vector<vector<int>>& events) {
int n = events.size();
int best = 0;
for (int i = 0; i < n; i++) {
best = max(best, events[i][2]);
for (int j = i + 1; j < n; j++) {
if (events[i][1] < events[j][0] || events[j][1] < events[i][0]) {
best = max(best, events[i][2] + events[j][2]);
}
}
}
return best;
}
};function maxTwoEvents(events) {
const n = events.length;
let best = 0;
for (let i = 0; i < n; i++) {
best = Math.max(best, events[i][2]);
for (let j = i + 1; j < n; j++) {
if (events[i][1] < events[j][0] || events[j][1] < events[i][0]) {
best = Math.max(best, events[i][2] + events[j][2]);
}
}
}
return best;
}2Optimal (sort + suffix max + binary search)
O(n log n)Sorting plus one binary search per event.O(n)The suffix-max array has n + 1 entries.Sort events by start day and build sufMax[i], the largest value among events i..n-1. For each event taken as the earlier one, binary search the first index j whose start is after its end; the best partner is then sufMax[j] (0 if none). Taking the event alone is covered by that 0.
- Sort events by start.
- Fill sufMax from right to left, with sufMax[n] = 0.
- For each event i, binary search the first j with events[j].start > events[i].end.
- best = max(best, events[i].value + sufMax[j]); return best.
class Solution {
public int maxTwoEvents(int[][] events) {
Arrays.sort(events, (p, q) -> Integer.compare(p[0], q[0]));
int n = events.length;
int[] sufMax = new int[n + 1];
for (int i = n - 1; i >= 0; i--) {
sufMax[i] = Math.max(sufMax[i + 1], events[i][2]);
}
int best = 0;
for (int i = 0; i < n; i++) {
int lo = i + 1, hi = n;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (events[mid][0] > events[i][1]) hi = mid;
else lo = mid + 1;
}
best = Math.max(best, events[i][2] + sufMax[lo]);
}
return best;
}
}class Solution:
def maxTwoEvents(self, events: List[List[int]]) -> int:
events.sort(key=lambda e: e[0])
n = len(events)
starts = [e[0] for e in events]
suf_max = [0] * (n + 1)
for i in range(n - 1, -1, -1):
suf_max[i] = max(suf_max[i + 1], events[i][2])
best = 0
for i, (s, e, v) in enumerate(events):
j = bisect.bisect_right(starts, e, i + 1)
best = max(best, v + suf_max[j])
return bestclass Solution {
public:
int maxTwoEvents(vector<vector<int>>& events) {
sort(events.begin(), events.end(),
[](const vector<int>& p, const vector<int>& q) { return p[0] < q[0]; });
int n = events.size();
vector<int> sufMax(n + 1, 0);
for (int i = n - 1; i >= 0; i--) {
sufMax[i] = max(sufMax[i + 1], events[i][2]);
}
int best = 0;
for (int i = 0; i < n; i++) {
int lo = i + 1, hi = n;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (events[mid][0] > events[i][1]) hi = mid;
else lo = mid + 1;
}
best = max(best, events[i][2] + sufMax[lo]);
}
return best;
}
};function maxTwoEvents(events) {
events.sort((p, q) => p[0] - q[0]);
const n = events.length;
const sufMax = new Array(n + 1).fill(0);
for (let i = n - 1; i >= 0; i--) {
sufMax[i] = Math.max(sufMax[i + 1], events[i][2]);
}
let best = 0;
for (let i = 0; i < n; i++) {
let lo = i + 1, hi = n;
while (lo < hi) {
const mid = (lo + hi) >>> 1;
if (events[mid][0] > events[i][1]) hi = mid;
else lo = mid + 1;
}
best = Math.max(best, events[i][2] + sufMax[lo]);
}
return best;
}Edge cases to test
- One event ends on the same day another starts: they overlap
- A single event is worth more than any compatible pair
- Every event overlaps every other one: the answer is the largest value
- Many events with the same start or end day
Hints
Hint 1
Fix the first event you attend. Among the events that start after it ends, you only care about the most valuable one.
Hint 2
If events are sorted by start time, 'every event starting after day d' is a suffix of the array.
Hint 3
Precompute the maximum value of every suffix, and find where the suffix begins with binary search.
FAQ
What is the best time complexity for Two Best Non-Overlapping Events?
Optimal (sort + suffix max + binary search) runs in O(n log n) time and O(n) extra space. Sorting plus one binary search per event.
Which pattern does Two Best Non-Overlapping Events use?
It is a intervals problem that uses the basics pattern. Other problems with the same pattern: Detect overlap unsorted, Detect overlap sorted intervals, Interval List Intersections.
Is there a brute force solution for Two Best Non-Overlapping Events?
Yes. Brute force (check every pair) takes O(n²) time and O(1) space. The answer is either one event alone or a pair of events that do not share any day.
Which edge cases should I test for Two Best Non-Overlapping Events?
One event ends on the same day another starts: they overlap; A single event is worth more than any compatible pair; Every event overlaps every other one: the answer is the largest value; Many events with the same start or end day.