AlgoMaster Logo

Two Best Non-Overlapping Events

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We have a list of events, each with a start time, end time, and value. We want to pick at most two events that don't overlap (one must finish strictly before the other starts) and maximize the total value.

The "at most two" part matters. Sometimes the best answer is a single high-value event, and pairing it with anything else either isn't possible or doesn't improve the total. We need to consider both the single-event case and the two-event case.

The expensive part is finding, for each event, the best event that ends before it starts. Sorting events lets us use binary search to locate compatible events, but we also need the maximum value among all events that end before a given time. That requires a precomputed prefix maximum.

Key Constraints:

  • 2 <= events.length <= 10^5 -- With up to 100,000 events, we need O(n log n) or better. An O(n^2) brute force checking every pair will be too slow.
  • 1 <= startTimei <= endTimei <= 10^9 -- Times can be very large, so we can't use arrays indexed by time. We need to work with the events themselves.
  • 1 <= valuei <= 10^6 -- Values are positive, so attending an event never hurts (the question is whether it conflicts with a better option).

Approach 1: Brute Force

Intuition

Try every pair of events, check whether they overlap, and track the maximum sum. We also consider each event on its own to cover the "pick just one" case.

Two events are non-overlapping when one finishes strictly before the other begins. Concretely, events [s1, e1, v1] and [s2, e2, v2] are compatible if e1 < s2 or e2 < s1. We check every pair against this condition.

Algorithm

  1. Initialize maxSum = 0.
  2. For each event i, update maxSum = max(maxSum, events[i].value) (single event case).
  3. For each pair of events (i, j) where i < j:
    • If event i ends before event j starts, or event j ends before event i starts, they are compatible.
    • Update maxSum = max(maxSum, events[i].value + events[j].value).
  4. Return maxSum.

Visualization and Code

Loading animation...

For each event we scan every other event to check compatibility, which is O(n) work per event. With n up to 100,000 that is around 10^10 comparisons, far too slow. Sorting the events lets us replace each linear scan with a binary search.

Approach 2: Sort by End Time + Binary Search with Prefix Maximum

Intuition

Sort events by end time and build a running maximum of values. For each event, binary search for the rightmost event that ends strictly before the current event starts. The prefix maximum at that position gives the best value achievable among all earlier-ending events.

Processing events in order of when they finish lets us maintain a "best value so far" array. When we reach an event starting at time s, we want the best single event that finishes before time s. Binary search on the sorted end times locates the rightmost such event in O(log n).

The answer is the maximum over all events of value[i] + bestValueEndingBefore(start[i]), together with each value[i] on its own.

Algorithm

  1. Sort events by end time.
  2. Build a prefixMaxValue array where prefixMaxValue[i] is the maximum value among events 0 through i (sorted by end time).
  3. For each event i (in sorted order):
    • Binary search in the sorted events for the rightmost event whose end time is strictly less than start[i].
    • If found at index j, the best pairing value is value[i] + prefixMaxValue[j].
    • Update the global answer with max(answer, value[i], value[i] + prefixMaxValue[j]).
  4. Return the global answer.

Visualization and Code

Loading animation...

This approach is O(n log n). The next approach reaches the same bound without a prefix max array or binary search, by processing event starts and ends as a single timeline sweep.

Approach 3: Sweep Line (Optimal)

Intuition

Instead of sorting by end time and binary searching, treat the problem as a timeline sweep. Each event contributes two time points: an end-time point (when it finishes and its value becomes available) and a start-time point (when it begins and may pair with an earlier event).

Sweep from left to right through time. When an event ends, update the best value seen so far. When an event starts, check whether pairing it with the best previously-ended event produces a new maximum.

Shifting end times to endTime + 1 makes an event ending at time t available only for events starting at t + 1 or later, which matches the strict-inequality rule. The sort then handles ordering on its own: at any equal time, end entries (type 0) sort before start entries (type 1), so a value becomes available before a same-time start tries to use it.

Algorithm

  1. Create a list of time points:
    • For each event, add (startTime, 1, value) -- type 1 means "start."
    • For each event, add (endTime + 1, 0, value) -- type 0 means "end" (value becomes available).
  2. Sort time points by time. Break ties by type (process type 0 "end" before type 1 "start" at the same time).
  3. Sweep through the time points, maintaining maxPrevValue (best value of any event that has ended):
    • If it's an "end" entry: update maxPrevValue = max(maxPrevValue, value).
    • If it's a "start" entry: update answer = max(answer, value + maxPrevValue).
  4. Return answer.

Visualization and Code

Loading animation...