Two Best Non-Overlapping Events
MedPrompt
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:
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:
Input: events = [[1,3,2],[4,5,2],[1,5,5]]
Output: 5
Explanation: Choose event 2 for a sum of 5.Example 3:
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 <= 105events[i].length == 31 <= startTimei <= endTimei <= 1091 <= valuei <= 106
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize
maxSumto 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]andevents[j]are non-overlapping (i.e.,events[i][1] < events[j][0]orevents[j][1] < events[i][0]) - If they are non-overlapping, update
maxSum = max(maxSum, events[i][2] + events[j][2]). - Return
maxSum.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Sort the
eventsarray bystartTime. - Create a
maxSuffixValuearray of sizen+1.maxSuffixValue[i]will store the maximum event value from indexiton-1. InitializemaxSuffixValue[n] = 0. - Populate
maxSuffixValueby iterating fromi = n-1down to0. - Initialize
maxSum = 0. - Iterate through each event
ifrom0ton-1. - For
events[i], use binary search to find the smallest indexj > isuch thatevents[j][0] > events[i][1]. - If a valid
jis found, the maximum value of a second event ismaxSuffixValue[j]. If not, the value ismaxSuffixValue[n] = 0. - Update
maxSum = max(maxSum, events[i][2] + maxSuffixValue[j]). - Return
maxSum.
Walkthrough
The algorithm proceeds as follows:
- Sort the
eventsarray based onstartTime. - Create a suffix maximum array,
maxSuffixValue, wheremaxSuffixValue[i]stores the maximum value of any event from indexito the end of the array. This can be computed in O(N) time with a single pass from right to left. - Iterate through each event
i. For this event, we need to find the best partner. The partner must start after eventiends. We use binary search on the start times of eventsi+1ton-1to find the indexjof the first event that starts afterevents[i][1]. - If such an index
jis found, the best partner for eventiwill have a value ofmaxSuffixValue[j]. We then update our global maximum sum withevents[i][2] + maxSuffixValue[j]. - 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.
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; }}Complexity
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).
Trade-offs
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.
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.
Algorithm
- Sort the
eventsarray bystartTime. - Initialize
maxSum = 0andmaxPrevValue = 0. - Initialize a min-priority queue,
pq, to store[endTime, value]pairs, ordered byendTime. - Iterate through each
eventin the sorted array: - While the
pqis not empty and theendTimeat the top of the queue is less than the current event'sstartTime: -
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 thepq. - Return
maxSum.
Walkthrough
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:
- We first look at our priority queue. Any event in the queue whose
endTimeis less than thecurrentEvent'sstartTimehas finished. We poll all such events from the queue. - As we poll these finished events, we keep track of the maximum value seen among them in a variable, let's call it
maxPrevValue. - Now,
maxPrevValuerepresents the value of the best event we can choose that is guaranteed to not overlap withcurrentEvent(since it finished beforecurrentEventstarted). - We can form a pair with
currentEventand this best previous event, giving a total value ofcurrentEvent.value + maxPrevValue. We update our globalmaxSumwith this potential value. - Finally, we add the
currentEvent(specifically, itsendTimeandvalue) 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.
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; }}Complexity
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).
Trade-offs
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.
Solutions
Solution
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; }}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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.