c++ | Memoization+Binary Search | Explaination
Solution-Memoization + Binary Search\n\nThought Process\n1. For every event, I\'ve two options. Whether I choose that event or not.\n2. If choose, then I add it
# Solution-Memoization + Binary Search\n\n*Thought Process*\n1. For every event, I\'ve two options. Whether I choose that event or not.\n2. If choose, then I add its value to my answer. If not choosen I move forward to the next event.\n3. Now if I select a event, my next event has to have `start time > end time of choosen event`. Also of all the possible next events I should choose the one with `max value`\n4.  To select the next event with `start time > end time of choosen event`, I can do a Binary search.\n5.  What to select the `Max value` I can find the value of all legal subsets possible, and select the maximum of all the values.\n\n```\n    vector<int> start;\n    int dp[100002][2];\n    \n    int solve(vector<vector<int>>& events, int i, int choose){\n        if(i>=events.size()){\n            return 0; \n        }       \n        \n        if(choose>=2){    // since I cannot chose more than two elemnts.\n            return 0;\n        }\n        \n        if(dp[i][choose]!=-1){\n            return dp[i][choose];\n        }\n        \n        int idx = upper_bound(start.begin(),start.end(),events[i][1])-start.begin(); // binary search to find the next event\'s index\n            \n        return dp[i][choose]=max(events[i][2]+solve(events,idx,choose+1),solve(events,i+1,choose)); //either I select an event, or I dont\n        \n    }\n    \n    int maxTwoEvents(vector<vector<int>>& events) {\n        \n        for(int i=0;i<100002;i++){\n            for(int j=0;j<2;j++){\n                dp[i][j]=-1;\n            }\n        }\n        int n = events.size();\n\t\t//sort elemts acc to start time\n        sort(events.begin(),events.end());\n\t\t\n        start.clear();\n        for(int i=0;i<n;i++){\n            start.push_back(events[i][0]);            \n        }\n        \n        return solve(events,0,0);\n    }\n```\n\n**Time Complexity - O[n*log(n)]**
['Dynamic Programming', 'Memoization', 'C', 'Binary Tree']