Two Best Non-Overlapping Events

Leetcode Problem:

• Two Best Non-Overlapping Events

Summary

• Given a 2D array of events where each event has a start time, end time, and value, find the maximum sum of two non-overlapping events.

Approach

• The approach is to first sort the events by their start time, then use dynamic programming to find the maximum sum of two non-overlapping events
• We also use a suffix maximum array to store the maximum value that can be obtained by attending the events up to each index.

Complexity

• O(n log n) due to the sorting of events, where n is the number of events.

Solution Code:

class Solution {
public:
    int maxTwoEvents(vector>& events) {
        int n = events.size();
        
        sort(events.begin(), events.end(), [](const vector& a, const vector& b) {
            return a[0] < b[0];
        });
        
        vector suffixMax(n);
        suffixMax[n - 1] = events[n - 1][2];
        
        for (int i = n - 2; i >= 0; --i) {
            suffixMax[i] = max(events[i][2], suffixMax[i + 1]);
        }
        
        int maxSum = 0;
        
        for (int i = 0; i < n; ++i) {
            int left = i + 1, right = n - 1;
            int nextEventIndex = -1;
            
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (events[mid][0] > events[i][1]) {
                    nextEventIndex = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            
            if (nextEventIndex != -1) {
                maxSum = max(maxSum, events[i][2] + suffixMax[nextEventIndex]);
            }
            
            maxSum = max(maxSum, events[i][2]);
        }
        
        return maxSum;
    }
};