Two Best Non-Overlapping Events

Medium
1443.

Two Best Non-Overlapping Events

Two Best Non-Overlapping Events is a medium coding problem on arrays, dynamic programming and sorting, asked in Amazon, Google and Razorpay interviews.

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^5
  • events[i].length == 3
  • 1 <= startTime <= endTime <= 10^9
  • 1 <= value <= 10^6
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} events
 * @return {number}
 */
var maxTwoEvents = function(events) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^5
  • events[i].length == 3
  • 1 <= startTime <= endTime <= 10^9
  • 1 <= value <= 10^6

Hints for Two Best Non-Overlapping Events

  1. Hint 1

    Fix the earlier of the two events. The best partner is the most valuable event that starts after it ends.

  2. Hint 2

    Sort events by start time and precompute a suffix maximum of values.

  3. 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

  1. Sort the events by startTime.
  2. Build suffix[i], the maximum value among events i..n-1.
  3. For each event, find the first index j with start[j] > end by binary search.
  4. The candidate is value + suffix[j] (just value if j == 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 best

Java

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