Best Value from Up to Two Separate Events
Company: Grammarly
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Each event has a start time, an end time and a value. Choose at most two events to attend, with no overlap between their inclusive time intervals, and return the greatest total value you can receive. An event that starts at the same time another ends overlaps that event; a later event must start strictly after the earlier one ends.
```cpp
class Solution {
public:
int maxTwoEvents(vector<vector<int>>& events);
};
```
### Examples
**Example 1:**
```text
events = [[1,2,4],[3,4,5],[2,3,8]]
Output: 9
Explanation: The first two events total 9; the value-8 event overlaps both.
```
**Example 2:**
```text
events = [[1,5,10],[2,3,2]]
Output: 10
Explanation: Taking just the first event is best.
```
### Constraints
- `2 <= events.length <= 10^5`.
- `1 <= start <= end <= 10^9`; `1 <= value <= 10^6`.
### Clarifying Questions
The limit is at most two. Compatible events require the next start strictly greater than the previous end.
```hint Inspect the structure
After sorting by start, how can you query the largest value among all later compatible events?
```
### Reasoning checkpoints
- Enforce inclusive time boundaries when deciding whether two events can both be attended.
- Compare the best valid pair with the best single event rather than requiring two events.
- Explain why no feasible selection of at most two events can have a greater total value.
### Optional extensions
How would you find the maximum value if at most k events could be attended?
Overview: Best Value from Up to Two Separate Events. Each event is [start,end,value] with inclusive times. Attend at most two events whose time intervals do not overlap, maximizing total value. Return that maximum. An event starting when another ends conflicts with it.