Maximum Number of Events That Can Be Attended II

A greedy algorithm seems to be impossible here as we are not able to pre-emptively exclude a meeting without considering all the other meetings around them.

Therefore, it makes sense to iterate through the entire solution space and use a dp algorithm to store our values and maximise our values from attending events. In our case, we have dp[i][j], where 0 <= i < k denotes the number of events we can afford to attend, and 0 <= j < events.size() denotes the index of the event we are currently on. Then, dp[i][j] denotes the maximum value we can attain after attending a maximum of i events and starting on event index j.

Now, we have a recursion recursive algorithm that aims to iterate through all events and, given an eventIndex and k value, aims to return the maximum value we can attain after attending a maximum of k events after starting on event index eventIndex.

During the recursion recursive algorithm, for each event we can choose to either:

• attend the event
  • if we attend, we can return the sum the current value of the event, and recursively run recursion with k-1 starting from the next possible event index
• NOT attend the event
  • if we don't, we can return the result after recursively running recursion with k starting from index eventIndex + 1

Since recursion returns the maximum value we can attain, by choosing the maximum possible value out of the results after attending or not attending the event, we can set dp[k][eventIndex] to that value, and simply return it.

This might make more sense if you read the code-

code

class Solution {
public:
    int recursion(int eventIndex, vector<vector<int>>& events, int k, vector<vector<int>> &dp) {
        if (eventIndex >= events.size() || eventIndex == -1 || k == 0) {
            return 0;
        }
        if (dp[k][eventIndex] != -1) {
            return dp[k][eventIndex];
        }

        int l = eventIndex;
        int r = events.size()-1;
        int res = -1;
        while (l <= r) {
            int mid = l + (r - l)/2;

            if (events[mid][0] > events[eventIndex][1]) {
                res = mid;
                r = mid-1;
            } else {
                l = mid+1;
            }
        }
        int outcome1 = events[eventIndex][2] + recursion(res, events, k-1, dp);
        int outcome2 = recursion(eventIndex+1, events, k, dp);

        dp[k][eventIndex] = max(outcome1, outcome2);
        return dp[k][eventIndex];
    }
    int maxValue(vector<vector<int>>& events, int k) {
        sort(events.begin(), events.end());
        vector<vector<int>> dp (k+1, vector<int>(events.size(), -1));
        return recursion(0, events, k, dp);
    }
};

complexity

• Time: O(n k log(n)) where n is the number of elements inside of events and k is just the input k
• Space: O(n k)

time taken

• 25 minutes and 47 seconds