Two Best Non-Overlapping Events

Medium Intervals Basics Original on LeetCode

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^5
  • events[i] = [start_i, end_i, value_i]
  • 1 <= start_i <= end_i <= 10^9
  • 1 <= 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.

00:00
Testcase

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.

ApproachTimeSpace
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)

TimeO(n²)All n(n - 1) / 2 pairs are checked.
SpaceO(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.

  1. best = max value of any single event.
  2. 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.
  3. 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;
    }
}

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.