# Two Best Non-Overlapping Events
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/two-best-non-overlapping-events)
Canonical: https://scaleengineer.com/dsa/problems/two-best-non-overlapping-events
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Heap (Priority Queue)
**Companies:** [razorpay](https://scaleengineer.com/companies/razorpay)
---
## Problem
You are given a **0-indexed** 2D integer array of `events` where `events[i] = [startTimei, endTimei, valuei]`. The `ith` event starts at `startTimei` and ends at `endTimei`, and if you attend this event, you will receive a value of `valuei`. You can choose **at most** **two** **non-overlapping** events to attend such that the sum of their values is **maximized**.

Return _this **maximum** sum._

Note that the start time and end time is **inclusive**: that is, you cannot attend two events where one of them starts and the other ends at the same time. More specifically, if you attend an event with end time `t`, the next event must start at or after `t + 1`.

**Example 1:**

![](https://assets.glich.co/dsa/two-best-non-overlapping-events/image0.png) 

**Input:** events = [[1,3,2],[4,5,2],[2,4,3]]
**Output:** 4
**Explanation:** Choose the green events, 0 and 1 for a sum of 2 + 2 = 4.

**Example 2:**

![Example 1 Diagram](https://assets.glich.co/dsa/two-best-non-overlapping-events/image1.png) 

**Input:** events = [[1,3,2],[4,5,2],[1,5,5]]
**Output:** 5
**Explanation:** Choose event 2 for a sum of 5.

**Example 3:**

![](https://assets.glich.co/dsa/two-best-non-overlapping-events/image2.png) 

**Input:** events = [[1,5,3],[1,5,1],[6,6,5]]
**Output:** 8
**Explanation:** Choose events 0 and 2 for a sum of 3 + 5 = 8.

**Constraints:**

* `2 <= events.length <= 105`
* `events[i].length == 3`
* `1 <= startTimei <= endTimei <= 109`
* `1 <= valuei <= 106`

# Approaches
## Brute Force Iteration
The most straightforward approach is to examine every possible combination of events. We can consider taking just one event or a pair of non-overlapping events. We iterate through all single events to find the maximum single value, and then iterate through all possible pairs of events, checking for the non-overlapping condition. If a pair is valid, we sum their values and update the overall maximum.
**Time:** O(N^2), where N is the number of events. The nested loops dominate the runtime, as we check approximately N^2 / 2 pairs. · **Space:** O(1), as we only use a constant amount of extra space for variables.
**Pros:** Very simple to conceptualize and implement.
**Cons:** Highly inefficient due to the nested loops.; Will result in a Time Limit Exceeded (TLE) error for large inputs as specified by the constraints.
### Explanation
This method involves two main parts. First, we find the maximum value attainable from a single event. We initialize our answer with this value. Second, we use nested loops to generate every unique pair of events `(i, j)`. For each pair, we check if they are non-overlapping. Two events `e1 = [s1, e1, v1]` and `e2 = [s2, e2, v2]` are non-overlapping if the first one ends before the second one starts (`e1 < s2`) or vice-versa (`e2 < s1`). If they don't overlap, we calculate their combined value `v1 + v2` and see if it's greater than the maximum sum found so far. After checking all pairs, the result is the maximum sum we've recorded.

```java
class Solution {
    public int maxTwoEvents(int[][] events) {
        int n = events.length;
        int maxVal = 0;

        // First, find the maximum value from any single event.
        for (int[] event : events) {
            maxVal = Math.max(maxVal, event[2]);
        }
        
        // Then, check all pairs of events for a non-overlapping combination.
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int[] e1 = events[i];
                int[] e2 = events[j];
                // Check for non-overlapping condition: one must end before the other starts.
                if (e1[1] < e2[0] || e2[1] < e1[0]) {
                    maxVal = Math.max(maxVal, e1[2] + e2[2]);
                }
            }
        }
        return maxVal;
    }
}
```
### Algorithm
- Initialize `maxSum` to 0.
- Iterate through all events to find the maximum single event value and update `maxSum`.
- Use a nested loop to iterate through every unique pair of events `(i, j)`.
- For each pair, check if `events[i]` and `events[j]` are non-overlapping (i.e., `events[i][1] < events[j][0]` or `events[j][1] < events[i][0]`)
- If they are non-overlapping, update `maxSum = max(maxSum, events[i][2] + events[j][2])`.
- Return `maxSum`.

## Sorting with Binary Search
To improve upon the brute-force method, we can avoid the O(N) scan for a second event. By sorting the events by their start times, we can use a more efficient search method. For each event `i`, we want to find the best possible non-overlapping event `j` that starts after `i` finishes. The condition is `events[j].startTime > events[i].endTime`. After sorting, all such potential events `j` will appear after `i` in the sorted array. We can find the first such `j` using binary search. To find the one with the maximum value efficiently, we can precompute the maximum value of any event in the suffixes of the sorted array.
**Time:** O(N log N). The initial sort takes O(N log N). The main loop runs N times, with each binary search taking O(log N), contributing another O(N log N). The pre-computation is O(N). Thus, the total complexity is dominated by sorting. · **Space:** O(N) for storing the `maxSuffixValue` array. The space for sorting depends on the implementation, but is often O(log N) or O(N).
**Pros:** Efficient enough to pass the given constraints.; Logically follows from optimizing the brute-force search.
**Cons:** Requires O(N) extra space for the suffix array.; The logic involves multiple steps: sorting, pre-computation, and a loop with binary search.
### Explanation
The algorithm proceeds as follows:
1. Sort the `events` array based on `startTime`.
2. Create a suffix maximum array, `maxSuffixValue`, where `maxSuffixValue[i]` stores the maximum value of any event from index `i` to the end of the array. This can be computed in O(N) time with a single pass from right to left.
3. Iterate through each event `i`. For this event, we need to find the best partner. The partner must start after event `i` ends. We use binary search on the start times of events `i+1` to `n-1` to find the index `j` of the first event that starts after `events[i][1]`.
4. If such an index `j` is found, the best partner for event `i` will have a value of `maxSuffixValue[j]`. We then update our global maximum sum with `events[i][2] + maxSuffixValue[j]`. 
5. The case of choosing a single event is implicitly handled because if no valid second event is found, we effectively add 0, comparing the global maximum with each single event's value.

```java
import java.util.Arrays;

class Solution {
    public int maxTwoEvents(int[][] events) {
        int n = events.length;
        Arrays.sort(events, (a, b) -> Integer.compare(a[0], b[0]));
        
        // maxSuffixValue[i] stores the max value in events[i...n-1]
        int[] maxSuffixValue = new int[n + 1];
        maxSuffixValue[n] = 0; // Sentinel value for no event found
        for (int i = n - 1; i >= 0; i--) {
            maxSuffixValue[i] = Math.max(maxSuffixValue[i + 1], events[i][2]);
        }
        
        int maxSum = 0;
        for (int i = 0; i < n; i++) {
            int endTime = events[i][1];
            
            // Binary search for the first event starting after endTime
            int low = i + 1, high = n - 1;
            int nextEventIndex = n; // Default to sentinel if no such event
            
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if (events[mid][0] > endTime) {
                    nextEventIndex = mid;
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            
            // Combine current event's value with the best possible second event's value
            maxSum = Math.max(maxSum, events[i][2] + maxSuffixValue[nextEventIndex]);
        }
        
        return maxSum;
    }
}
```
### Algorithm
- Sort the `events` array by `startTime`.
- Create a `maxSuffixValue` array of size `n+1`. `maxSuffixValue[i]` will store the maximum event value from index `i` to `n-1`. Initialize `maxSuffixValue[n] = 0`.
- Populate `maxSuffixValue` by iterating from `i = n-1` down to `0`.
- Initialize `maxSum = 0`.
- Iterate through each event `i` from `0` to `n-1`.
- For `events[i]`, use binary search to find the smallest index `j > i` such that `events[j][0] > events[i][1]`.
- If a valid `j` is found, the maximum value of a second event is `maxSuffixValue[j]`. If not, the value is `maxSuffixValue[n] = 0`.
- Update `maxSum = max(maxSum, events[i][2] + maxSuffixValue[j])`.
- Return `maxSum`.

## Sweep-line with Priority Queue
A more elegant and common pattern for interval-based problems is the sweep-line algorithm. We process events chronologically by sorting them based on their start times. As we iterate through the events, we maintain the maximum value of any event that has *already finished*. This allows us to find the best possible first event to pair with the current event in an efficient manner.
**Time:** O(N log N). Sorting takes O(N log N). Each of the N events is pushed onto and popped from the priority queue exactly once. Each priority queue operation takes O(log N) time. Therefore, the loop also contributes O(N log N) to the complexity. · **Space:** O(N). In the worst-case scenario, the priority queue might hold all N events (e.g., if all events start before the first one ends).
**Pros:** An elegant and efficient single-pass approach (after sorting).; It's a powerful and versatile technique for many interval problems.
**Cons:** The logic involving the priority queue might be slightly less intuitive at first glance compared to the binary search approach.
### Explanation
The core idea is to iterate through events sorted by `startTime`. We use a min-priority queue to keep track of the `(endTime, value)` of events that are currently in progress. For each `currentEvent` we process:
1. We first look at our priority queue. Any event in the queue whose `endTime` is less than the `currentEvent`'s `startTime` has finished. We poll all such events from the queue.
2. As we poll these finished events, we keep track of the maximum value seen among them in a variable, let's call it `maxPrevValue`.
3. Now, `maxPrevValue` represents the value of the best event we can choose that is guaranteed to not overlap with `currentEvent` (since it finished before `currentEvent` started).
4. We can form a pair with `currentEvent` and this best previous event, giving a total value of `currentEvent.value + maxPrevValue`. We update our global `maxSum` with this potential value.
5. Finally, we add the `currentEvent` (specifically, its `endTime` and `value`) to the priority queue, as it is now an 'in-progress' event.
This single pass after sorting correctly finds the maximum sum, covering both single and two-event cases.

```java
import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int maxTwoEvents(int[][] events) {
        Arrays.sort(events, (a, b) -> Integer.compare(a[0], b[0]));
        
        // Min-heap stores [endTime, value] for events in progress, ordered by endTime.
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        
        int maxSum = 0;
        int maxPrevValue = 0; // Tracks the max value of any event that has already finished.
        
        for (int[] currentEvent : events) {
            int start = currentEvent[0];
            int value = currentEvent[2];
            
            // Clear the PQ of events that finished before this one started.
            // Update maxPrevValue with the values of these finished events.
            while (!pq.isEmpty() && pq.peek()[0] < start) {
                int[] finishedEvent = pq.poll();
                maxPrevValue = Math.max(maxPrevValue, finishedEvent[1]);
            }
            
            // The best pair for the current event uses the best finished event found so far.
            // This also handles the single-event case since maxPrevValue is initially 0.
            maxSum = Math.max(maxSum, value + maxPrevValue);
            
            // Add the current event to the set of in-progress events.
            pq.offer(new int[]{currentEvent[1], value});
        }
        
        return maxSum;
    }
}
```
### Algorithm
- Sort the `events` array by `startTime`.
- Initialize `maxSum = 0` and `maxPrevValue = 0`.
- Initialize a min-priority queue, `pq`, to store `[endTime, value]` pairs, ordered by `endTime`.
- Iterate through each `event` in the sorted array:
-   While the `pq` is not empty and the `endTime` at the top of the queue is less than the current event's `startTime`:
-     Poll the event from the queue.
-     Update `maxPrevValue` with the polled event's value if it's larger.
-   Update `maxSum = max(maxSum, event.value + maxPrevValue)`.
-   Offer the current event's `[endTime, value]` to the `pq`.
- Return `maxSum`.

# Solutions
### Java

```java
class Solution {
public
  int maxTwoEvents(int[][] events) {
    Arrays.sort(events, (a, b)->a[0] - b[0]);
    int n = events.length;
    int[] f = new int[n + 1];
    for (int i = n - 1; i >= 0; --i) {
      f[i] = Math.max(f[i + 1], events[i][2]);
    }
    int ans = 0;
    for (int[] e : events) {
      int v = e[2];
      int left = 0, right = n;
      while (left < right) {
        int mid = (left + right) >> 1;
        if (events[mid][0] > e[1]) {
          right = mid;
        } else {
          left = mid + 1;
        }
      }
      if (left < n) {
        v += f[left];
      }
      ans = Math.max(ans, v);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxTwoEvents(vector<vector<int>> &events) {
    sort(events.begin(), events.end());
    int n = events.size();
    vector<int> f(n + 1);
    for (int i = n - 1; ~i; --i)
      f[i] = max(f[i + 1], events[i][2]);
    int ans = 0;
    for (auto &e : events) {
      int v = e[2];
      int left = 0, right = n;
      while (left < right) {
        int mid = (left + right) >> 1;
        if (events[mid][0] > e[1])
          right = mid;
        else
          left = mid + 1;
      }
      if (left < n)
        v += f[left];
      ans = max(ans, v);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxTwoEvents(self, events: List[List[int]]) -> int: events . sort() n = len(events) f = [events[- 1][2]] * n for i in range(n - 2, - 1, - 1): f[i] = max(f[i + 1], events[i][2]) ans = 0 for _, e, v in events: idx = bisect_right(events, e, key=lambda x: x[0]) if idx < n: v += f[idx] ans = max(ans, v) return ans

```