Two Best Non-Overlapping Events

medium sorting binary search suffix maximum

Problem

You are given events where events[i] = [start, end, value]. The start and end times are inclusive, so two events overlap if one starts at or before the other ends. Choose at most two non-overlapping events to attend so that the sum of their values is maximized, and return that maximum sum. An event chosen after one ending at time t must start at t + 1 or later.

Inputevents = [[1,3,2],[4,5,2],[2,4,3]]

Output4

Attend [1,3,2] then [4,5,2] (they don't overlap) for 2 + 2 = 4.

Inputevents = [[1,5,3],[1,5,1],[6,6,5]]

Output8

Attend [1,5,3] then [6,6,5] for 3 + 5 = 8.

events (start:end:value, comma-separated)

def max_two_events(events):
    events.sort(key=lambda e: e[0])         # sort by start time
    n = len(events)
    suffix = [0] * (n + 1)                   # suffix[i] = max value in events[i:]
    for i in range(n - 1, -1, -1):
        suffix[i] = max(suffix[i + 1], events[i][2])
    best = 0
    for s, e, v in events:
        lo, hi = 0, n                        # find first start > e
        while lo < hi:
            mid = (lo + hi) // 2
            if events[mid][0] > e:
                hi = mid
            else:
                lo = mid + 1
        best = max(best, v + suffix[lo])
    return best

function maxTwoEvents(events) {
  events.sort((a, b) => a[0] - b[0]);        // sort by start time
  const n = events.length;
  const suffix = new Array(n + 1).fill(0);   // suffix[i] = max value in events[i:]
  for (let i = n - 1; i >= 0; i--) {
    suffix[i] = Math.max(suffix[i + 1], events[i][2]);
  }
  let best = 0;
  for (const [s, e, v] of events) {
    let lo = 0, hi = n;                       // find first start > e
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (events[mid][0] > e) hi = mid;
      else lo = mid + 1;
    }
    best = Math.max(best, v + suffix[lo]);
  }
  return best;
}

int maxTwoEvents(int[][] events) {
    Arrays.sort(events, (a, b) -> a[0] - b[0]);   // sort by start time
    int n = events.length;
    int[] suffix = new int[n + 1];                // suffix[i] = max value in events[i:]
    for (int i = n - 1; i >= 0; i--)
        suffix[i] = Math.max(suffix[i + 1], events[i][2]);
    int best = 0;
    for (int[] ev : events) {
        int e = ev[1], v = ev[2];
        int lo = 0, hi = n;                       // find first start > e
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (events[mid][0] > e) hi = mid;
            else lo = mid + 1;
        }
        best = Math.max(best, v + suffix[lo]);
    }
    return best;
}

int maxTwoEvents(vector<vector<int>>& events) {
    sort(events.begin(), events.end());           // sort by start time
    int n = events.size();
    vector<int> suffix(n + 1, 0);                  // suffix[i] = max value in events[i:]
    for (int i = n - 1; i >= 0; i--)
        suffix[i] = max(suffix[i + 1], events[i][2]);
    int best = 0;
    for (auto& ev : events) {
        int e = ev[1], v = ev[2];
        int lo = 0, hi = n;                        // find first start > e
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (events[mid][0] > e) hi = mid;
            else lo = mid + 1;
        }
        best = max(best, v + suffix[lo]);
    }
    return best;
}

Explanation

We may pick at most two events, and they must not overlap. The key idea: once we fix the first event, the best partner is simply the highest-value event whose start time is strictly after the first event's end. So the whole problem reduces to "for each event, what is the best non-overlapping event that comes later?"

To answer that fast, first sort events by start time. Then build a suffix array where suffix[i] is the maximum value among all events from index i to the end. We fill it right to left: suffix[i] = max(suffix[i+1], value[i]).

Now take each event as the first pick. Its end time is e. We need the first sorted index whose start time is > e — every event from there on is a valid, non-overlapping partner. Because starts are sorted, a binary search finds that boundary index lo in O(log n).

The best partner value is then suffix[lo] (it is 0 if no later event exists, which means we just attend one event). We update best = max(best, v + suffix[lo]) and move on.

This pairs a sorting / suffix-max precomputation with a binary search per event — the same flavor as the priority-queue sweep solution, but with an explicit suffix array. Overall it runs in O(n log n) time.

Time: O(n log n) Space: O(n)