Two Best Non-Overlapping Events solution

Problem Statement

Link to the problem statement

Intuition & Approach

Here is some intuition of my solution:

1. Sort by the start point and store each end point

2. DP formulation:

   • $dp[i][0]$ $\rightarrow$ maximum value using exactly one event, where that event is i
   • $dp[i][1]$ $\rightarrow$ maximum value using exactly two events, where the first event is i
   • $dp[i][1] = v + max(dp[j][0])$, where $n > j > i$ and $e[i]$ not overlaps with $e[j]$
   • $dp[m][0] = v\ \forall m \in [0, n)$

3. how to find the starting index of j? binary search (lower bound in C++)

4. how to find the max quickly? suffix max

Complexity

• Time complexity:

• Space complexity:

Code

C++ solution:

#define MAX(A, B) ((A) > (B) ? (A) : (B))
class Solution {
public:
    int maxTwoEvents(vector<vector<int>>& events) {

        sort(events.begin(), events.end());
        const int n = events.size();

        vector<int> start(n);

        vector<int> sufmax(n + 1, 0);
        for (int i = n - 1; i >= 0; i--) {
            start[i] = events[i][0];
            sufmax[i] = MAX(sufmax[i + 1],  events[i][2]);
        }

        int ans = 0;

        for (int i = 0; i < n; i++) {
            int j = lower_bound(start.begin(), start.end(), events[i][1] + 1) - start.begin();
            int dp1 = events[i][2] + sufmax[j];
            ans = MAX(ans, dp1);
        }

        return ans;
    }
};

Python solution:

from bisect import bisect_left

class Solution:
    def maxTwoEvents(self, events):
        events.sort()
        n = len(events)

        start = [0] * n

        sufmax = [0] * (n + 1)

        for i in range(n - 1, -1, -1):
            start[i] = events[i][0]
            sufmax[i] = max(sufmax[i + 1], events[i][2])

        ans = 0

        for i in range(n):
            j = bisect_left(start, events[i][1] + 1)
            dp1 = events[i][2] + sufmax[j]
            ans = max(ans, dp1)

        return ans